<title>Fractal dimension estimation using the fast continuous wavelet transform</title>

M. J. Vrhel, Chulhee Lee, Michaël UnserProceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE 1995 · DOI

TL;DR

This paper introduces a novel, computationally efficient algorithm for estimating fractal dimensions of signals using the Continuous Wavelet Transform (CWT). By approximating wavelets with compactly supported scaling functions, they achieve O(N) complexity per scale, a significant improvement over traditional O(N log N) methods, while maintaining control over approximation accuracy.

What Problem Does This Paper Address?

Estimating fractal dimensions is crucial for characterizing complex signals found in fields like turbulence and diffusion-limited aggregation. A popular wavelet-based method, the Wavelet Transform Modulus Maxima (WTMM) method, relies on the CWT. However, this method requires computing the CWT at many fine, non-dyadic scales to accurately capture the signal's self-similarity. This fine sampling, combined with the inherent computational cost of the CWT, makes the process very slow, especially for long signals. Traditional CWT implementations, often Fourier-based, have a complexity of O(N log N) per scale, which becomes a bottleneck. The paper aims to address this computational inefficiency by developing a faster CWT algorithm suitable for fractal dimension estimation.

Methods

The core innovation is a "fast continuous wavelet transform" (FCWT) algorithm. Instead of directly computing the CWT, which is computationally expensive, the authors approximate the analyzing wavelet by projecting it onto a subspace spanned by a compactly supported scaling function. This approximation allows for efficient computation using a duality principle and recursive digital filtering.

Key aspects of their method include:

  • Compactly Supported Scaling Function: They leverage a scaling function that has finite support, which simplifies calculations and enables efficient filter design.
  • Approximation of Wavelets: The analyzing wavelets are approximated by orthogonal projections onto the subspace defined by the scaling function. This allows for control over the approximation error.
  • Recursive Digital Filtering: The algorithm utilizes a recursive filtering approach, similar to what's used in discrete wavelet transforms, to compute wavelet coefficients efficiently.
  • O(N) Complexity per Scale: By using this approximation and filtering strategy, they achieve a computational complexity of O(N) operations per scale, a substantial improvement over the O(N log N) of FFT-based methods.
  • Control over Accuracy: The paper provides theoretical bounds on the approximation error and demonstrates how to achieve any desired level of accuracy by adjusting parameters like the scaling function's order or the scale sampling.

Datasets

The paper does not explicitly mention or introduce specific "datasets" in the traditional machine learning sense. Instead, they use a generalized devil staircase signal (shown in Figure 6) as a synthetic multi-fractal signal with a known dimension for evaluating their algorithm's performance.

Key Insights and Ideas

  • Bridging the Gap between Continuous and Discrete Wavelets: The method effectively bridges the gap between the theoretical elegance of continuous wavelets for fractal analysis and the computational practicality of discrete, filter-bank-like implementations.
  • Efficiency without Sacrificing Accuracy: The key insight is that by carefully approximating wavelets with compactly supported functions, one can achieve significant computational speedups (O(N) vs. O(N log N)) without compromising the accuracy required for fractal dimension estimation.
  • Tunable Accuracy: The ability to control and guarantee approximation error is crucial. This means researchers can choose a trade-off between computational cost and precision based on their specific needs.
  • General Applicability: The framework is presented as a general method for computing CWTs at arbitrary scales, making it applicable beyond just fractal dimension estimation.

Key Results

The paper demonstrates the effectiveness of their fast CWT algorithm in estimating the generalized fractal dimensions of a multi-fractal signal.

  • Computational Speedup: The primary result is the achievement of O(N) complexity per scale for the CWT, compared to O(N log N) for traditional methods. This is a significant efficiency gain for analyzing long signals.
  • Accurate Fractal Dimension Estimation: When applied to a generalized devil staircase signal, the algorithm successfully estimated its fractal dimensions. Figure 9 shows a close agreement between the estimated and exact values of τ(q) = (q-1)Dq, indicating the method's accuracy.
  • Error Control: The paper shows that the approximation error can be bounded and controlled, as illustrated in Figure 3, which plots RMS error against scale for different approximation types.

Limitations and Future Work

  • Approximation Error: While controllable, the approximation inherently introduces some error. The paper discusses how to manage this error by selecting appropriate scaling functions and scales. The trade-off is that achieving higher accuracy might require longer FIR filters, increasing computational cost slightly.
  • Initialization for Recursive Filters: The practical implementation of recursive filters requires careful initialization, especially at signal boundaries. The paper mentions using mirror boundary conditions to address this.
  • Future Work: The paper implicitly suggests that this fast CWT algorithm can be applied to a wider range of fractal signal analysis problems and potentially other signal processing tasks where CWT is beneficial. The ability to control accuracy also opens doors for more robust and efficient analyses in various scientific domains.

Summary updated

Abstract

We first review a method for the characterization of fractal signals introduced by Muzy et al. This approach uses the continuous wavelet transform (CWT) and considers how the wavelet values scale along maxima lines. The method requires a fine scale sampling of the signal and standard dyadic algorithms are not applicable. For this reason, a significant amount of computation is spent evaluating the CWT. To improve the efficiency of the fractal estimation, we introduced a general framework for a faster computation of the CWT. The method allows arbitrary sampling along the scale axis, and achieves O(N) complexity per scale where N is the length of the signal. Our approach makes use of a compactly supported scaling function to approximate the analyzing wavelet. We discuss the theory of the fast wavelet algorithm which uses a duality principle and recursive digital filtering for rapid calculation of the CWT. We also provide error bounds on the wavelet approximation and show how to obtain any desired level of accuracy. Finally, we demonstrate the effectiveness of the algorithm by using it in the estimation of the generalized dimensions of a multi-fractal signal.
BibTeX
@inproceedings{vrhel1995lt,
  author = {M. J. Vrhel and Chulhee Lee and Michaël Unser},
  title = {{\<title\>Fractal dimension estimation using the fast continuous wavelet transform\</title\>}},
  booktitle = {Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE},
  year = {1995},
  doi = {10.1117/12.217603},
}

Loading related content...

Figure