There are many models for analyzing and synthesizing 2D data at a variety of different scales and directions. Characterizing directional information in data is significant since it provides information on the location of key objects in the data. These locations in turn are used to describe where these objects are relative to each other. However, often these models only account for a given set of directions, and, furthermore, they tend to be computationally intensive. For example, the theoretical developments described in the large number of published articles on wavelet transforms provides for data exploitation along horizontal, vertical, and diagonal directions as well as multiple scales. However, several techniques have been devised to model and exploit 2D data along multiple directions.1 Other state-of-the-art methods in sparse directional representations include contourlets,2 curvelets,3 shearlets,4 and multidirectional wavelets.5 These methods have been extensively analyzed, and their success in providing near optimal geometric decompositions of signals has been established.2–5 As mentioned, these models are often difficult to implement, and their high-dimensional analogs are still not well understood.
We propose a computationally efficient model for analyzing 1D and 2D multiscale and multidirectional data. The model is based on a mathematical concept known as tight frames. Redundancy is a desirable property for many applications, including signal denoising,6 classification,7 sparse representations of signals,8, 9 and compressive sensing.10 It is in relation to the last two applications that we see the biggest potential of frames in creating representation models that can be optimized for a specific application. The proposed models are an extension of earlier reported research.11, 12 That work demonstrated that by using the proper choice of functions, the models can remove directional smooth content in 2D data and at the same time effectively characterize the underlying variation information that is required in many geostatistical applications.
Constructing a frame can be difficult, and often the available mathematical algorithms generate frames by minimizing functions on complex manifolds.13–16 This procedure becomes more computationally complex as the dimension of the data grows. In contrast to these models, we constructed our frames from a set of linearly independent analysis and synthesis vectors. We did this by using a simple procedure that combines their circular convolution and interpolation by zeros. These analysis and synthesis operators are computationally fast because of a representation that allows the algorithm to be implemented in a separable manner. Some of the advantages of our formulation include reduced complexity in implementation, computational cost, memory usage, and, for applications involving edges, an increased range of detected directions. The original formulation employed these models to characterize variational information as well as to remove smooth content in data. Other applications may include image denoising and compression. Although we designed the mathematical formulation for real vectors, the results can be easily extended to include complex vectors. It is usually the case that the latter functions could potentially provide a much richer and larger set of models that may be used to analyze data. Our mathematical formulation can also be extended to 3D data and data sets in higher dimensions.
The proposed method allows us to generate a large number of models that are a function of scale and direction, which are employed to extract information such as edges in 2D data. The vectors may include various types of wavelet bases. However, the models are not limited to these functions. As mentioned, we combined algebraic and geometric properties with lattice theory to generate our directional and multiscale operators. Perfect reconstruction or synthesis of the data was guaranteed by the proposed models by simply transposing the analysis operator. Specifically, the proposed functions allowed us to do multiscale and multidirectional edge detection, noise reduction, optimal sparse reconstructions, lossy and lossless reconstruction, and super resolution. In this study, we investigated the super resolution of images, demonstrating that we can super resolve an image without blurring edges by choosing the direction of an edge (see Figure 1).
Figure 1. Radial lines varying in intensity and originating from the origin at 0°, 14.03°, 26.51°, 36.86°, 45°, 53.13°, 63.43°, 75.96° and 90°.
Bicubic interpolation (left) and directional tight frames (right). This is twice the resolution of Figure 1
Figure 2 is twice the resolution of Figure 1. The left side illustrates the results of a bicubic interpolation scheme applied to Figure 1, while the right side shows our multiscale and multidirectional technique. Note that the lines at 0°, 14.03°, 26.51°, 63.43° and 75.96° are well interpolated without blurring edges. However, our technique does not perform well interpolating the 36.86° and the 53.13° lines. Preliminary results suggest that the set of tight frames used in our analysis did not include a sufficiently large number of directions. We anticipate that these results can be improved by simply increasing the number of directional functions as well as the scale. In the near future, we intend to further extend our multiscale and directional framework and apply it to the problem of image denoising and compression.
Edward Bosch, Alexey Castrodad, John Cooper
National Geospatial-Intelligence Agency
Edward Bosch works for the US government developing remote sensing mathematical models for the exploitation of digital data. He has a BS and MS in mathematics, and a PhD in computational mathematics. His current research is on the subject of mathematical frames which are an extension of a basis for vector spaces.
Julia Dobrosotskaya, Wojciech Czaja
University of Maryland
College Park, MD
1. Y. Tanaka, M. Hasegawa, S. Kato, M. Ikehara, T. Q. Nguyen, Adaptive directional wavelet transform based on directional prefiltering, IEEE Trans. Image Process. 19(4), p. 934-945, 2010.
2. M. N. Do, M. Vetterli, The contourlet transform: an efficient directional multiresolution image representation, IEEE Trans. Image Process. 14(12), p. 2091-2106, 2005.
3. E. J. Candes, D. L. Donoho, Curvelets and curvilinear integrals, J. Approx. Theory 113, p. 59-90, 2000.
4. D. Labate, W. Lim, G. Kutyniok, G. Weiss, Sparse multidimensional representation using shearlets, Proc. SPIE
5914, p. 254-262, 2005. doi:10.1117/12.613494
5. V. Velisavljevic, B. Beferull-Lozano, M. Vetterli, P. L. Dragotti, Discrete multidirectional wavelet bases, Proc. Int'l. Conf. Image Process. 1, p. 1025-1028, 2003.
6. L. Shen, M. Papadakis, I. A. Kakadiaris, I. Konstantinidis, D. Kouri, D. Hoffman, Image denoising using a tight frame, IEEE Trans. Image Process. 15(5), 2006.
7. J. Benedetto, W. Czaja, J. Flake, M. Hirn, Frame-based kernel methods for automatic classification in hyperspectral data, IEEE Int'l. Geosci. and Remote Sensing Symp. (4), p. 697-700, 2009.
8. A. Castrodad, Z. Xing, J. Greer, E. Bosch, L. Carin, G. Sapiro, Discriminative sparse representations in hyperspectral imagery, IEEE Int'l. Conf. Image Process. , 2010.
9. A. Castrodad, Z. Xing, J. B. Greer, E. Bosch, L. Carin, G. Sapiro, Learning discriminative Sparse Representations for modeling, source separation, and mapping of hyperspectral imagery, IEEE Trans. Geosci. and Remote Sensing 49(11), 2011.
10. A. A. Moghadam, M. Aghagolzadeh, M. Kumar, H. Radha, Incoherent color frames for compressive demosaicing, IEEE Int'l. Conf. Acoustics, Speech and Signal Process., p. 22-27, 2011.
11. E. Bosch, M. O. Oliver, R. Webster, Wavelets and the generalization of the variogram, Math. Geol. 36(2), 2004.
12. E. Bosch, A. P. Gonzalez, J. G. Vivas, G. R. Easley, Directional wavelets and a wavelet variogram for two-dimensional data, Math. Geosci., 2009.
13. J. J. Benedetto, M. Fickus, Finite normalized tight frames, Adv. Comp. Math. 18, p. 357-385, 2003.
14. J. Cahill, M. Fickus, D. G. Mixon, M. J. Poteet, N. Strawn. Constructing finite frames of a given spectrum and set of lengths (preprint).
15. N. Strawn, Geometric structures and optimization on spaces of finite frames, PhD thesis, University of Maryland, College Park, MD, 2011.
16. W. Czaja, Remarks on Naimark's duality, Proc. Amer. Math. Soc. 136, p. 867-871, 2008.