University of Calgary

Computing algorithm

May 31, 2011

Fast S-Transform

By Kelly Sansom

The S-Transform has several areas of applications including medical imaging, such as identifying abnormalities in brain tumours.The S-Transform has several areas of applications including medical imaging, such as identifying abnormalities in brain tumours.Robb Brown remembers well that weekend he was working as an electrical engineering graduate student in the Schulich School of Engineering translating data using the S-Transform—a transform ideal for applications studying frequency changes of a signal over time and space.

The computation would take the entire weekend to produce the required data. Looking for a way to save time, he decided to run the computation using multiple computers rather than a single computer. What originally would take the entire weekend, now took just over a day.

That same year, while attending a conference, Brown shared with a fellow attendee the results of his work using multiple computers. Reducing the time from three days to one day is a significant improvement, he remembers his colleague saying, but it is still too time-consuming and requires too much memory storage for any real practical use. “Some smart grad student will come along some day and figure out how to do it faster,” Brown recalls replying. Little did he know that he would be the one to figure out this challenge.

Continuing his work in a research lab run by Dr. Richard Frayne—Canada Research Chair in Image Science and Hopewell professor of brain imaging in the radiology, and clinical neurosciences departments at the Hotchkiss Brain Institute—Brown developed a computationally efficient algorithm for calculating the S-Transform. Named the Fast S-Transform, this new algorithm has shown on preliminary testing to significantly reduce the time and memory requirements for computation.

In an experiment using an ECG recording from a patient complaining of angina, the hour-long recording which usually would have taken at least three days and up to 16 TB of space now took only 0.77 seconds and 4 MB of space to transform. The Fast S-Transform algorithm can be performed in both the time domain and the frequency domain. The original time domain algorithm was developed by Brown and later extended to the frequency domain by Dr. Louis Lauzon, research professor at the Seaman Family Centre at Foothills Medical Centre and the University of Calgary.

The S-Transform has several areas of applications including medical imaging, such as detecting anomalies in the heart, and identifying abnormalities in brain tumours, as well as detecting disturbances in power networks, monitoring wind patterns, detecting gravitational waves and monitoring sound and acoustic patterns.

However, due to its complex computation requirements, it has not been widely used. Now, with the new Fast S-Transform, the complex computation requirements are removed, increasing its potential usage for more practical applications.

Working with University Technologies International, the Fast S-Transform (FST) has been made available to the research community under an open source license. Packages to use the FST in C and Python can be downloaded from Sourceforge at sourceforge.net/projects/fst-uofc. For more information, contact Robert Carruthers, project manager, engineering and physical sciences, University Technologies International: Carruthers@uti.ca or 403-270-2446.


Bookmark and Share