Practical Applications of Wavelet-Based Multiresolution Displays

Tom Mathews

Grand Valley State University

MTH 380 Semester Project

December 4, 2001

1.0 Introduction

With the introduction of modern technologies such as digital image processing, Finite Element Analysis, digital satellite mapping, and powerful computer simulation programs, the amount of data available to researchers and scientists has grown to immense proportions. Unfortunately, the development of technology to acquire data has far outpaced the development of technology to read, store, transmit, and utilize the data. The storage and communication difficulties associated with the FBI’s fingerprint files are popular examples (Aboufadel 2-4). However, even if today’s computers could store these huge amounts of data and could communicate with enough speed, the impracticality of working with huge data sets would remain. For instance, satellite measurements can often produce gigabytes or terabytes of data (Gerstner 1). However, when used in the field, much of the data may be either irrelevant to the user or unnecessarily detailed. To this end, wavelets have been employed in many fields of study to make large data sets more manageable while compromising little in terms of accuracy and true representation of the original data. In particular, the use of multiresolution analysis (MRA) allows the user to approximate the original data as much as he or she likes. Operating in a fashion similar to the focus adjustment on a camera or projector, multiresolution analysis is a convenient way to retrieve only as much information as needed from a large data set.

It is the goal of this paper to investigate more fully the use and acceptability of multiresolution analysis in practical applications. In particular, the application to the display of coastline data and global topographical data will be explored, as well as general extensions to both applications. Other utilizations of wavelet-based and/or multiresolution analyses in the study of geophysics will also briefly be examined.

2.0 Multiresolution Analysis

A multiresolution analysis is defined as a nested sequence of subspaces of L²(R) with a scaling function such that the following conditions are met (Aboufadel 53-54).

(1.0)

Stollnitz gives a simple explanation of the MRA.

“As j increases, the resolution of functions in V^j increases. The basis functions for the space V^j are known as scaling functions. The next step in multiresolution analysis is to define wavelet spaces. For each j, we define W^j as the orthogonal complement of V^j in V^j+1. This means that W^j includes all the functions in V^j+1 that are orthogonal to all those in V^j under some chosen inner product. The functions we choose as a basis for W^j are called wavelets (1).”

As a result of the MRA, any function in L²(R) can be approximated by a linear combination of the scaling functions in V_j, .

3.0 Multiresolution Display of Coastline Data

A coastline, when viewed from above, is really a series of arcs and lines connected to form a certain shape. In two dimensions, the coastline can be modeled as a curve. Typically, when a geological feature like a coastline is mapped by satellite, it is given in coordinate or point form. Therefore, the problem becomes approximating a curve based on a given number of points. Graphically a curve is usually formed by a set of points of intersection, the satellite point data, and connecting line segments (Kobayashi 1). To reduce the number of points describing the curve and consequently the data, a subset of the original points or a linear combination of a functions can be used. Eliminating data points at the outset will remove information that cannot be retrieved later on, and depending on the descriptiveness of the original data could produce grossly unsatisfactory results. Instead, wavelet methods are preferred for four reasons:

1. Scaling functions and wavelets are localized in space so that sharp spikes can be represented easily and accurately

2. The fractal-like features of some types of scaling functions and wavelets resemble the intricate zigzags found in most coastlines

3. Scaling functions and wavelets can be used to approximate broad cusps in coastlines by setting the appropriate coefficients in the expansion to be very large

4. Computations to move through various resolution levels using dyadic wavelets can be made very efficient by using techniques analogous to fast Fourier methods (2).

3.1 Mallat’s Algorithm

In the Japanese research study, “Wavelet-Based Multiresolution Display of Coastline Data” by Hiyama and Kobayashi, a technique called Mallat’s algorithm is applied to the approximation and display of curves. Mallat’s algorithm can be though of as a combination of the dilation equation and a multiresolution analysis. Meaning that, in general, if V_n is a closed subspace, then any function, , can be written as a sum of the scaling functions, φ(x) of V_n-1 and the wavelet functions ψ(x) of W_n-1 (5). Mallat’s algorithm for the closed subspace V₁ is defined as:

From the Orthogonal Decomposition Theorem, since , C¹ can be written in terms of D⁰ and C⁰ as

3.2 Using Mallat’s Algorithm

Hiyama and Kobayashi used four types of wavelets in their experiment to find which types of wavelets were best suited for approximating coastline data via Mallat’s algorithm. Daubechies’ orthonormal and Coiflets wavelets were chosen because computations with them are simple and because their inherent fractal-like features are representative of a typical coastline. However, neither wavelet type is symmetric; therefore, results may differ depending on which side of a function computations are started from. In light of this, two types of symmetric biorthogonal wavelets were also considered, Daubechies’ biorthogonal wavelets and biorthogonal splines (Kobayashi 6). The Daubechies’ orthonormal wavelets will be used to demonstrate how Mallat’s algorithm is applied and a short description of the others will also be included.

3.2.1 Mallat’s Algorithm Using Daubechies’ Orthonormal Wavelets

Before implementing Mallat’s algorithm, the functions for the father and mother wavelets must be determined. Hiyama and Kobayashi define the orthonormal scaling function as:

Where η_l is determined iteratively by

Where χ is the characteristic function, and α(i) are filter coefficients (7).

Consequently, the orthonormal wavelet function with N vanishing moments is defined as:

The filter coefficients for these wavelets were given in a table based upon the number of vanishing moments, from N=2…7 (8). The compact support of these wavelets has width 2N-1.

The data for a given curve is given as a set of points, P={p₀, p₁,…p_n}. Following the notation in equation 1.1, , where n=2^k-1. Next, Mallat’s algorithm is used to break C¹ into a set of coefficients . The algorithm is applied again to . This process is continued as many times as possible as long as the desired accuracy of the curve approximation is retained. When a coefficient has a very small value, it is replaced with a zero to further reduce the data (11-12).

3.2.2 Coiflets

Coiflets, a term coined by Daubechies in honor of their inventor, R. Coifmann, are a group of orthonormal scaling functions and wavelets that both have vanishing moments. Like Daubechies’ orthonormal scaling and wavelet functions, Coiflets must be computed from their filter coefficients. Unlike Daubechies’ orthonormal wavelets and scaling functions, Coiflets are not orthonormal; they are, however, more symmetric. Coiflets also have compact support, though it is much wider at 6N-1, for N vanishing moments (9).

3.2.3 Symmetric Biorthogonal Wavelets

Because Daubechies’ orthonormal and Coiflets scaling and wavelet functions are not symmetric, different approximations can be obtained depending on which side the computations are started from. Therefore, two types of symmetric biorthogonal wavelets, Daubechies’ biorthogonal wavelets and biorthogonal splines, were also studied by Hiyama and Kobayashi. The filter coefficients for biorthogonal splines and Daubechies’ biorthogonal wavelets can be obtained from Tables 8.2 and 8.5 respectively in Daubechies’ Ten Lectures on Wavelets.

3.3 Experimental Curve Approximation Results

In the study conducted by Hiyama and Kobayashi, three “types” of curves were examined for wavelet-based approximation, spiral curves, Kuri curves, and coastlines. The purpose of using different curves was to find the strengths and weaknesses of each type of wavelet in varying conditions, as each family of curves has unique properties. As expected, each wavelet had varying degrees of success and was best suited to a particular kind of curve. A summary of their performance by curve type follows.

3.3.1 Spiral Curves

Spiral curves belong to a family of curves having the form

For this type of curve, the best approximations resulted from the C₂, B₂, D₃, and S_1,3 wavelets, where the subscript denotes the degree of the filter coefficients. Coiflets and Daubechies’ biorthogonal wavelets were stable with respect to changes in the degree of the filter coefficients while biorthogonal splines and Daubechies’ orthonormal wavelets were not. The best approximations of each type of wavelet produced perfect reconstructions, at least as distinguishable from the resolution of a computer screen (14).

3.3.2 Kuri Curves

Kuri curves belong to a family of curves having the form

For this type of curve, the best approximations resulted from the C₆, B₂, D₃, and S_1,5 wavelets, where the subscript denotes the degree of the filter coefficients. Overall, a marked difference in the performance of different degrees of Daubechies’ orthonormal wavelets was noted as the number of data points was reduced. The same change was not experienced with the other three types of wavelets (15-16).

3.3.3 Coastlines

As previously noted, most coastlines have jagged and smooth elements, both of which must be recreated in an approximation. To test each wavelet’s performance on the coastline data, the original data set, consisting of 256 points, was reduced to 128 points and then to 64 points. For 128 data points, the best results were produced by the C₂, B₂, D₄, and S_1,3 wavelets. In this case, the Daubechies’ orthonormal wavelets produced inaccuracies in sections of the coastline that were smooth while the biorthogonal spline wavelets missed detailed features in the jagged sections. The spline wavelet approximations were deemed unsuitable for this application as they produced approximation curves that sometimes intersected themselves. Overall, the Coiflets wavelets produced the most accurate and stable results.

For 64 data points, the best results were produced by the C₁, B₁, D₃, and S_1,3 wavelets. Again, the Daubechies’ orthonormal and biorthogonal spline wavelets produced poor representations of the original curve, while the Coiflets and Daubechies’ biorthogonal wavelets were stable and accurate.

The results of the study show that not all wavelets are well suited to approximating coastline data. In particular, the Daubechies’ orthonormal and biorthogonal spline wavelets were too inaccurate for this application. Coiflets and Daubechies’ biorthogonal wavelets; however, seem to be particularly useful (17-19).

3.4 General Extensions

Since a coastline is essentially a curve, this method of approximation could have possible uses far beyond that of regenerating coastline data. It could be extended to graphics programs such as AutoCAD or Pro E for quick views or generating previews. This would also be suited to the processing of digital images; enlargements or box views, for example. In fact, Mallat’s algorithm has been applied to digital image processing (5). Other notable possibilities include mapping of atmospheric and ocean currents and tracking of flight trajectories.

4.0 Multiresolution Display of Global Topographical Data

Many of the same problems associated with the storing, processing, and transmitting of satellite-generated digital coastline data are shared by global topographical data. Because topographical data is usually viewed in three dimensions, the problems are of even greater magnitude. Several techniques have been developed to improve data access and search operations, concentration on specific parts of the data, and efficient storage of large data sets. The following sections will explore some of these techniques in greater depth and suggest general extensions to other applications.

4.1 Multiresolution Digital Elevation Models

For three-dimensional display of global data, the earth can be viewed as a single sphere. Multiresolution digital elevation models (DEM) are formed by recursive triangular bisection of the sphere in geographic coordinates (Gerstner 2). Each step in the multiresolution analysis produces more triangles and a finer resolution. Also, an error indicator is assigned to each triangle at each step. A hard thresholding value, ε, is then chosen, and any triangle which has an absolute value of the indicator larger than ε is set to zero.

Gerstner defines a digital elevation model as, “A set of points, and interpolation rules to derive height values in between. An interpolation rule usually incorporates information on how (e.g. a polynomial degree) and from where (e.g. a local mesh topology) data is interpolated. The height values h(x_i,y_i) are always fixed given data and have to be stored for every DEM” (3). Because of this, DEMs can be grouped according to the amount of additional storage space they require. If the order of the additional storage is O(N), the data set can be called explicit. If the order is less, the data set is called implicit. There are four basic classes of DEMs, which are listed below in order of increasing storage requirements and approximation quality (3). Examples of each class are shown in figure 2.

1. Implicit coordinates and interpolation – regular grids (Figure 2a) and graded meshes (Figure 2b).

2. Implicit coordinates and explicit interpolation – quadtrees (Figure 2c) and adaptive tensor product grids (Figure 2d).

3. Explicit coordinates and implicit interpolation – TINs, Delaunay triangulations (Figure 2e), and relocated regular grids (Figure 2f).

4. Explicit coordinates and interpolation – data-dependent triangulations (figure 2g) and general tesselations (Figure 2h).

Figure 2 – Examples of Various Methods of Implementing Digital Elevation Models

Courtesy of Gerstner p 3.

To begin a multiresolution DEM, a series of approximations of an input DEM must be determined. This can be achieved via Mallat’s algorithm or a similar method of approximation. Next, the method of implementation must be chosen. Pyramidal, incremental, and tree-structured are the three basic types of multiresolution DEMs. Pyramidal DEMs are composed of a handful of approximate DEMs having different resolutions. Incremental DEMs code the single insertion steps of a refinement method, such as Mallat’s algorithm, or the removal steps of a decimation method. Tree-structured DEMs can process and display only small subsets of data and are therefore better suited for specific visualization purposes. Pyramidal and incremental DEMs only lend themselves to global approximations, while tree-structured DEMs can also produce localized refinement (4). This is desirable in an application where only a region of a large country needs to be viewed.

The method of recursive bisection used by Gerstner is called longest edge bisection or split newest vertex triangulation. Basically, a coarse triangulation is made into multiple finer triangulations by dividing the triangle in two and then repeated a specified number of times. The midpoint of the bisected edge is called the refinement vertex, and an error indicator is assigned to each one. If the error indicator values are saturated, that is the indicator value of every triangle is greater than or equal to the indicator values of all of its subtriangles, then a valid triangulation can be generated (6). Triangles having an error indicator value greater than a preset threshold can be disregarded. The remaining triangles will then form a valid triangulation.

Wavelets can be applied in the formulation of the error indicators. Since the error indicators use height values and refinement vertex values, wavelets can be applied to compress this data by eliminating long, continuous strings in the data, such as global areas having straight lines where the refinement vertex error indicators would be small or zero. Figure three shows how wavelets were used in the error indicators to compensate for the poles of a sphere. Notice the obvious difference in triangle geometry near the poles of the figure on the right and the corrected figure on the left.

Figure 3 – Compensation for Poles Using Wavelets in the Error Indicators

Courtesy of Gerstner p. 16

4.2 Local Oracles

Local Oracles allow for the control of local approximations in specific regions of interest. According to Staadt, spatial localization of the basis functions enables the accentuation of particular wavelets while suppressing others. Thus, a straightforward oracle consists of a weighting function that operates on the coefficients of the wavelet transform. To apply an oracle, an ellipsoidal area must be assumed to apply the weighting function. This area is the region of interest. Staadt also states, “Localization of the wavelet transform enables the projection of scaled and translated versions of it into wavelet space, where individual coefficients are influenced” (4). In other words, only the localized region is affected by the weighting function.

4.3 General Extensions

Since topographical data is similar in many ways to the coastline data discussed previously, the multiresolution techniques discussed above could have some of the same applications. However, since topographical data is generally given in three dimensions, the possible uses are even more numerous. One application of local oracles that immediately comes to mind is digital image processing. As more and more photographs are taken and/or processed as digital images, the demand for rapid and user-friendly ways to process images is ever increasing. Often, especially in surveillance or reconnaissance photographs, only a small portion of a much larger image is of interest. Imagine how convenient it would be to take these kinds of photos at ultrahigh resolution, use wavelet-based image compression to display an approximated image quickly on a PC, and then use local oracles to view small areas of interest at the original, high resolution. Since this technology would be of great use to the military, it is likely that it has already been perfected, though no one may be aware of it. Multiresolution digital elevation models would be useful for quick display of images, where brevity rather than intricacy is desired, such as in graphics viewing programs or solid modeling programs. Another appropriate, though less humanistic, application would be in movie or cartoon animation. The morphing of shapes is an overused and typically unrealistic favorite of moviemakers; consequently, it would probably make more use of multiresolution DEMs than anything else. Perhaps a wavelet-based liquid metal man for the next Terminator film is in the works at this very moment.

5.0 Other Applications

Wavelets have been used successfully in other areas of geophysical study. Orthonormal wavelets, for instance, have been applied to the study of atmospheric layer turbulence. In one study by J.F. Howell and L. Mahrt, turbulence measurements were taken over a nine-hour period and analyzed using wavelet decomposition (Foufoula-Georgiou 81-101). In another study by Brunet and Collineau, turbulence data recorded over a corn crop was analyzed using the wavelet transform (130-148).

Wavelets have also been used to analyze seafloor bathymetry, or the topography of the ocean floor. In one study by Sarah Little, the use of wavelet analysis revealed patterns, trends, and structures that may be overlooked in raw data. Also, the use of methods like local oracles allowed for separation of data in regions of interest (167-181).

Several other geophysical applications such as analysis of marine seismic data and characterization of hydraulic conductivity distributions have also been used. The usefulness of wavelets in data analysis is clear, particularly in the field of geophysics, where large and cumbersome data sets abound. Studies such as the atmospheric layer turbulence and corn crop turbulence have further shown the proficiency of wavelets in the analysis of time-dependent data sets.

6.0 Discussion and Conclusion

The advent of the digital age has brought with it many powerful methods of gathering data and information. Accompanying the huge amounts of data has been a frustrating lack of technology to store, transmit, and analyze it. However, a rapidly growing field in wavelets seems uniquely suited to handling this data crisis. In particular, the application of wavelets to the approximation and visualization of coastline and topographical data has helped scientists and researchers manage the huge data sets generated by satellite imaging. Approximation techniques like multiresolution analysis, Mallat’s algorithm, and digital elevation models are at the heart of these applications of wavelets. One must remember, however, that these are approximation methods and cannot be applied blindly. Hiyama’s analysis of coastline data demonstrated that though multiple types of wavelets could satisfactorily approximate the coastline data, the degree and the type of the wavelet were critical to obtaining accurate results. Despite this, wavelets and, to a larger extent, multiresolution analysis have proven to be well suited for this type of analysis. And as the digital trend continues and data sets become larger, wavelet-based analysis will likely continue to find more applications both in and out of the realm of geophysics.

10.0 Works Cited

1. Aboufadel, Edward, et al. Discovering Wavelets. New York: John Wiley & Sons, 1999.

2. Daubechies, Ingrid. Ten Lectures on Wavelets. Philadelphia: SIAM, 1992.

3. Foufoula-Georgiou, Efi, et al. Eds. Wavelets in Geophysics. San Diego: Academic Press, 1994.

4. Gerstner, Thomas. “Multiresolution Visualization of Global Topographic Data”. Germany: University of Bonn Publications.

5. Kobayashi, Mei. Ed. Wavelets and Their Applications. Philadelphia: SIAM, 1998.

6. Staadt, Oliver. “Multiresolution Compression and Reconstruction”. Zurich: ETH Publications.

7. Stollnitz, Eric. Wavelets for Computer Graphics. San Francisco: Morgan-Kaufmann, 1996.