Fast S-Transform with O(NlogN) Complexity
Tech ID #: 770.2 CONNECT WITH A MANAGER FOR LICENSING
Description of Technology
Researchers at the University of Calgary have developed a novel algorithm that solves the S-Transform with O(NlogN) computational complexity. This Fast S-Transform algorithm is fully invertible and requires only O(N) storage space, such that its performance is consistent with the Fast Fourier Transform and Discrete Wavelet Transform. The new transform can be performed in both the time domain and the frequency domain.
The S-Transform is a frequency transform that is used to analyze the temporal frequency content of non-stationary signals. By using a progressive frequency resolution similar to the Wavelet Transform, it improves on the performance of the Short-Time Fourier Transform. Unlike the Wavelet, however, the S-Transform maintains a clear relationship to the Fourier spectrum. The transform is ideal for applications studying frequency changes of a signal over time and space. It has been found to be valuable in medical imaging applications such as detecting anomalies in the heart, identifying abnormalities in brain tumours, analyzing ECGs, and transmitting images. Outside of medical imaging, it has been used to characterize liquid crystals, detecting disturbances in power networks, monitoring wind patterns, and detecting gravitational waves. Previous implementations of the S-Transform have a computational complexity of O(N2logN) and a storage complexity of O(N2), which is an unreasonable computational burden when transforming anything other than very small signals.
The Fast S-Transform (FST) has been made freely available open source under the GNU General Public License v3.0 (GPLv3). FST packages in C and Python can be downloaded from Sourceforge at http://sourceforge.net/projects/fst-uofc/.
Non-free version of FST are available under terms different from those of the GPLv3. For more information, please contact firstname.lastname@example.org.
Areas of Application
The S-Transform can be used in most applications that currently use the Wavelet Transform, or used to extract more signal information in applications that currently use the Fourier Transform. Select application areas include:
- Medical imaging
- Image transmission/compression
- Sound/Acoustic engineering
- Financial Engineering
- Deep learning
- Patent - US 8458240 B2
- Brown, R.A., Lauzon, M.L., and Frayne, R., “A General Description of Linear Time-Frequency Transforms and Formulation of a Fast, Invertible Transform That Samples the Continuous S-Transform Spectrum Nonredundantly,” IEEE Trans. Signal Process. vol. 58, pp. 281-290, Jan 2010
- Brown, R.A., and Frayne, R., “A fast discrete S-transform for biomedical signal processing”, 30th Annual International Conference of the IEEE Engineering in Medicine and Biology Society (EMBS 2008), Vancouver, BC, 20-25 Aug 2008, pp. 2586-2589
- Stockwell, R.G., Mansinha, L., and Lowe, R.P., “Localization of the Complex Spectrum: the S-Transform”, IEEE Transactions on Signal Processing, vol. 44, pp. 998-1001, 1996
- Significantly decreased computation time and memory requirements
- Data can be transformed "in place"
- Can transform in less than a second data that previous methods would require over three days to complete
Stage Of Development
- Algorithm developed and tested in C
- Implemented in an embedded DSP system