Constant-Q transform

In mathematics and signal processing, the constant-Q transform and variable-Q transform, simply known as CQT and VQT, transforms a data series to the frequency domain. It is related to the Fourier transform and very closely related to the complex Morlet wavelet transform. Its design is suited for musical representation.

Constant-Q transform applied to the waveform of a C major piano chord. The x-axis is frequency, mapped to standard musical pitches, from low (left) to high (right). The y-axis is time, starting from pressing the piano chord at the bottom, and releasing the piano chord at the top, 8 seconds later. Darker pixels correspond to higher values of the Constant-Q transform. The peaks correspond closely to the precise frequencies of the vibrating piano strings. Thus the peaks can be used to detect the notes played on the piano. The lowest 3 peaks are the fundamental frequencies of the C major chord (C, E, G). Each string also vibrates at multiples of the fundamental, known as overtones, which correspond to the remaining smaller peaks to the right of the fundamental pitches. The overtones are smaller in intensity than the fundamental pitch.
Audio of the C Major piano chord used to generate the Constant-Q transform above.
Its waveform does not visually communicate pitch information like the Constant-Q transform is able to do.

The transform can be thought of as a series of filters fk, logarithmically spaced in frequency, with the k-th filter having a spectral width δfk equal to a multiple of the previous filter's width:

δfk=21/n⋅δfk−1=(21/n)k⋅δfmin,

where δfk is the bandwidth of the k-th filter, fmin is the central frequency of the lowest filter, and n is the number of filters per octave.

Calculation

The short-time Fourier transform of x[n] for a frame shifted to sample m is calculated as follows:

X[k,m]=∑n=0N−1W[n−m]x[n]e−j2πkn/N.

Given a data series at sampling frequency fs = 1/T, T being the sampling period of our data, for each frequency bin we can define the following:

Q=fkδfk.

For geometrically spaced bands, δfk=fk(21/n−1), so Q=(21/n−1)−1 is the same for every band and is in general not a whole number, being about 16.8 for n = 12 bins per octave. It is the number of cycles of the sinusoid spanned by the analysis window at fk, and so fixes the duration of that window.

N[k]=fsδfk=fsfkQ.
Since fs/fk is the number of samples processed per cycle at frequency fk, Q is the number of integer cycles processed at this central frequency, which need not be a whole number.

The equivalent transform kernel can be found by using the following substitutions:

N=N[k]=Qfsfk.
W[k,n]=α−(1−α)cos⁡2πnN[k]−1,α=25/46,0⩽n⩽N[k]−1.

After these modifications, we are left with

X[k]=1N[k]∑n=0N[k]−1W[k,n]x[n]e−j2πQnN[k].

Variable-Q bandwidth calculation

The variable-Q transform is the same as constant-Q transform, but the only difference is the filter Q is variable, hence the name variable-Q transform. The variable-Q transform is useful where time resolution on low frequencies is important[examples needed]. There are ways to calculate the bandwidth of the VQT, one of them using equivalent rectangular bandwidth as a value for VQT bin's bandwidth.


The variable-Q transform is usually obtained by adding a bandwidth offset γ, so that the bandwidth of the k-th band becomes

δfk=αfk+γ,

where α = 1/Q is fixed by the number of bands per octave. Setting γ = 0 recovers the constant-Q transform, while γ > 0 widens the lower bands, which lowers their Q and shortens their windows, improving time resolution at low frequencies at the cost of frequency resolution. Choosing γ so that each bandwidth is a fixed fraction of the equivalent rectangular bandwidth at the corresponding centre frequency gives bands following an auditory scale, and is the default in some implementations.


Fast calculation

The direct calculation of the constant-Q transform (either using naive discrete Fourier transform or slightly faster Goertzel algorithm) is slow when compared against the fast Fourier transform. However, the fast Fourier transform can itself be employed, in conjunction with the use of a kernel, to perform the equivalent calculation but much faster. An approximate inverse to such an implementation was proposed in 2006; it works by going back to the discrete Fourier transform, and is only suitable for pitch instruments.

A development on this method with improved invertibility involves performing CQT (via fast Fourier transform) octave-by-octave, using lowpass filtered and downsampled results for consecutively lower pitches. Implementations of this method include the MATLAB implementation and LibROSA's Python implementation. LibROSA combines the subsampled method with the direct fast Fourier transform method (which it dubs "pseudo-CQT") by having the latter process higher frequencies as a whole.

The sliding discrete Fourier transform can be used for faster calculation of constant-Q transform, since the sliding discrete Fourier transform does not have to be linear-frequency spacing and same window size per bin.

Alternatively, the constant-Q transform can be approximated by using multiple fast Fourier transforms of different window sizes and/or sampling rate at different frequency ranges then stitch it together. This is called multiresolution short-time Fourier transform, however the window sizes for multiresolution fast Fourier transforms are different per-octave, rather than per-bin.[ambiguous]

Invertible constant-Q transforms from nonstationary Gabor frames

The constant-Q transform can be cast as a nonstationary Gabor system, in which the analysis window varies with frequency rather than with time. Each band is formed by multiplying the Fourier transform of the signal by a real window centred on that band, then taking an inverse Fourier transform whose length matches the bandwidth of that window, so each band carries its own number of time coefficients.

If the windows satisfy a "painless" condition, so that at every frequency bin the sum of their squared magnitudes, each weighted by the number of coefficients in its band, is strictly positive, then the [[Frame (linear algebra)|frame]] operator is diagonal. It is then inverted by one division per bin, giving a dual window for each band, and synthesis from these dual windows recovers the signal exactly, with no iterative step; reconstruction is therefore exact up to numerical precision rather than approximate. Analysis and synthesis each cost one fast Fourier transform of the whole signal together with one short transform per band.

A sliced variant cuts the signal into overlapping slices under a smooth window, transforms each slice, and overlap-adds the inverses, which lets the transform run on a continuous stream with bounded memory and an algorithmic delay of one slice. The same construction with bands spaced on an auditory scale instead of geometrically gives the ERBlet transform. Reference implementations are published by the authors and in MATLAB's Wavelet Toolbox.

Comparison with the Fourier transform

In general, the transform is well suited to musical data, and this can be seen in some of its advantages compared to the fast Fourier transform. As the output of the transform is effectively amplitude/phase against log frequency, fewer frequency bins are required to cover a given range effectively, and this proves useful where frequencies span several octaves. As the range of human hearing covers approximately ten octaves from 20 Hz to around 20 kHz, this reduction in output data is significant.

The transform exhibits a reduction in frequency resolution with higher frequency bins, which is desirable for auditory applications. The transform mirrors the human auditory system, whereby at lower-frequencies spectral resolution is better, whereas temporal resolution improves at higher frequencies. At the bottom of the piano scale (about 30 Hz), a difference of 1 semitone is a difference of approximately 1.5 Hz, whereas at the top of the musical scale (about 5 kHz), a difference of 1 semitone is a difference of approximately 200 Hz. So for musical data the exponential frequency resolution of constant-Q transform is ideal.

In addition, the harmonics of musical notes form a pattern characteristic of the timbre of the instrument in this transform. Assuming the same relative strengths of each harmonic, as the fundamental frequency changes, the relative position of these harmonics remains constant. This can make identification of instruments much easier. The constant Q transform can also be used for automatic recognition of musical keys based on accumulated chroma content.

Relative to the Fourier transform, implementation of this transform is more tricky. This is due to the varying number of samples used in the calculation of each frequency bin, which also affects the length of any windowing function implemented.

Also note that because the frequency scale is logarithmic, there is no true zero-frequency / DC term present, which may be a drawback in applications that are interested in the DC term. Although for applications that are not interested in the DC such as audio, this is not a drawback.

References

  1. 1 2 Judith C. Brown, Calculation of a constant Q spectral transform, J. Acoust. Soc. Am., 89(1):425–434, 1991.
  2. ↑ Continuous Wavelet Transform "When the mother wavelet can be interpreted as a windowed sinusoid (such as the Morlet wavelet), the wavelet transform can be interpreted as a constant-Q Fourier transform. Before the theory of wavelets, constant-Q Fourier transforms (such as obtained from a classic third-octave filter bank) were not easy to invert, because the basis signals were not orthogonal."
  3. ↑ Cwitkowitz, Frank C.Jr (2019). "End-to-End Music Transcription Using Fine-Tuned Variable-Q Filterbanks" (PDF). Rochester Institute of Technology: 32–34. Retrieved 2022-08-21.
  4. 1 2 {{cite conference |last1=Schörkhuber |first1=Christian |last2=Klapuri |first2=Anssi |last3=Holighaus |first3=Nicki |last4=Dörfler |first4=Monika |title=A Matlab toolbox for efficient perfect reconstruction time-frequency transforms with log-frequency resolution |conference=AES 53rd International Conference on Semantic Audio |location=London |date=January 2014}}
  5. ↑ McFee, Brian. "librosa: core/constantq.py". GitHub. librosa. Retrieved 3 November 2026.
  6. ↑ Judith C. Brown and Miller S. Puckette, An efficient algorithm for the calculation of a constant Q transform, J. Acoust. Soc. Am., 92(5):2698–2701, 1992.
  7. ↑ FitzGerald, Derry; Cychowski, Marcin T.; Cranitch, Matt (1 May 2006). "Towards an Inverse Constant Q Transform". Audio Engineering Society Convention. 120. Paris: Audio Engineering Society.
  8. ↑ Schörkhuber, Christian; Klapuri, Anssi (2010). Constant-Q Transform Toolbox for Music Processing. 7th Sound and Music Computing Conference. Barcelona. Retrieved 12 December 2018. paper Archived 2020-12-01 at the Wayback Machine
  9. 1 2 McFee, Brian; Battenberg, Eric; Lostanlen, Vincent; Thomé, Carl (12 December 2018). "librosa: core/constantq.py at 8d26423". GitHub. librosa. Retrieved 12 December 2018.
  10. ↑ Bradford, R, ffitch, J & Dobson, R 2008, Sliding with a constant-Q, in 11th International Conference on Digital Audio Effects (DAFx-08) Proceedings September 1-4th, 2008 Espoo, Finland . DAFx, Espoo, Finland, pp. 363-369, Proc. of the Int. Conf. on Digital Audio Effects (DAFx-08), 1/09/08.
  11. ↑ Kırbız, S.; Günsel, B. (December 2014). "A multiresolution non-negative tensor factorization approach for single channel sound source separation". Signal Processing. 105: 56–69. Bibcode:2014SigPr.105...56K. doi:10.1016/j.sigpro.2014.05.019. ISSN 0165-1684.
  12. ↑ Balazs, Peter; Dörfler, Monika; Jaillet, Florent; Holighaus, Nicki; Velasco, Gino Angelo (2011). "Theory, implementation and applications of nonstationary Gabor frames". Journal of Computational and Applied Mathematics. 236 (6): 1481–1496. Bibcode:2011JCoAM.236.1481B. doi:10.1016/j.cam.2011.09.011. PMC 3257872. PMID 22267893.
  13. 1 2 3 Velasco, Gino Angelo; Holighaus, Nicki; Dörfler, Monika; Grill, Thomas (2011). Constructing an invertible constant-Q transform with nonstationary Gabor frames. 14th International Conference on Digital Audio Effects (DAFx-11). Paris. pp. 93–99.
  14. ↑ Daubechies, Ingrid; Grossmann, Alex; Meyer, Yves (1986). "Painless nonorthogonal expansions". Journal of Mathematical Physics. 27 (5): 1271–1283. Bibcode:1986JMP....27.1271D. doi:10.1063/1.527388.
  15. ↑ Holighaus, Nicki; Dörfler, Monika; Velasco, Gino Angelo M.; Grill, Thomas (2013). "A Framework for Invertible, Real-Time Constant-Q Transforms". IEEE Transactions on Audio, Speech, and Language Processing. 21 (4): 775–785. arXiv:1210.0084. Bibcode:2013ITASL..21..775H. doi:10.1109/TASL.2012.2234114.
  16. ↑ Necciari, Thibaud; Balazs, Peter; Holighaus, Nicki; Søndergaard, Peter L. (2013). The ERBlet transform: An auditory-based time-frequency representation with perfect reconstruction. 2013 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP). Vancouver. pp. 498–502. doi:10.1109/ICASSP.2013.6637697.
  17. ↑ "Constant-Q transform with nonstationary Gabor frames". NuHAG, University of Vienna.
  18. ↑ "Nonstationary Gabor Frames". MathWorks.
  19. ↑ Hendrik Purwins, Benjamin Blankertz and Klaus Obermayer, A New Method for Tracking Modulations in Tonal Music in Audio Data Format, International Joint Conference on Neural Network (IJCNN’00)., 6:270-275, 2000.
  20. ↑ Benjamin Blankertz, The Constant Q Transform, 1999.