A message from our CEO about the future of Stack Overflow and Stack Exchange. Read now.
20

You can use logarithms to get rid of the division. For $(x, y)$ in the first quadrant: $$z = \log_2(y)-\log_2(x)\\ \text{atan2}(y, x) = \text{atan}(y/x) = \text{atan}(2^z)$$ Figure 1. Plot of $\text{atan}(2^z)$ You would need to approximate $\text{atan}(2^z)$ in range $-30 < z < 30$ to get your required accuracy of 1E-9. You can take advantage of ...


20

The naive implementation of an $N$-point DFT is basically a multiplication by a $N \times N$ matrix. This results in a complexity of $\mathcal{O}(N^2)$. One of the most common Fast Fourier Transform (FFT) algorithm is the radix-2 Cooley-Tukey Decimation-in-Time FFT algorithm. This is a basic divide and conquer approach. First define the "twiddle factor" ...


19

http://nbviewer.jupyter.org/gist/leftaroundabout/83df89a7d3bdc24373ea470fb50be629 DFT, size 16 FFT, size 16 The difference in complexity is pretty evident from that, isn't it? Here's how I understand FFT. First off, I would always think about Fourier transforms foremostly as transforms of continuous functions, i.e. a bijective mapping $\operatorname{FT} ...


18

The physically "correct" way to do this is summing the samples. However when you add two arbitrary samples, the resulting value could be up to twice the maximum value. ... The naive solution here is to divide by N, where N is the number of channels being mixed. That's not the "naive" solution, its the only solution. That's what every analog and digital ...


17

I fear that all answers here are irrelevant to the question. What is called a vocoder in the music production world has little to do with the phase vocoder used in signal processing. To make matters worse the Songify app referenced by the original post is not an example of vocoder. Let us sort this out! 1. Phase vocoder The phase vocoder referenced by the ...


15

First of all, there's no such thing as 'template' in this paper - the word 'template(s)' has a different meaning in Computer Vision. The method used in this paper is relatively straight-forward. Let me break it down for you. There are three important things that you need to do when doing tasks such as object recognition, image matching, image stitching, ...


15

It's very hard to point you to relevant techniques without knowing any context for your problem. The obvious answer would be to tell you to adjust the gain of each sample so that clipping rarely occurs. It is not that unrealistic to assume that musicians would play softer in an ensemble than when asked to play solo. The distortion introduced by A + B - AB ...


15

Here is a picture to add to Robert's good answer demonstrating the "re-use" of operations, in this case for an 8 point DFT. The "Twiddle Factors" are represented in the diagram using the notation $W_N^{nk}$ which is equal to $e^{j2\pi \frac{nk}{N}}$ Note the path shown and the equation underneath shows the result for the frequency bin X(1), as given by ...


14

I would be tempted to reply "none", or "both classification and clustering". Why "none"? Because HMMs are not in the same bag as support vector machines or k-means. Support vector machines or k-means are specifically designed to solve a problem (classification in the first case, clustering in the second), and are indeed just an optimization procedure to ...


13

One method that works if there's a relatively strong drum beat is to take the magnitude of the STFT of the waveform, and then auto-correlate it in only the time dimension. The peak of the auto-correlation function will be the beat, or a submultiple of it. This is equivalent to breaking up the signal into a lot of different frequency bands, finding the ...


13

This is a well-studied problem, dating back from the mid 90s (DARPA/NIST broadcast transcription challenges). Search for "speech/music segmentation" or "audio segmentation" and you'll find thousands of research papers. There are two broad approaches to solve this problem: Supervised classification Train a speech/music classifier, using a standard machine ...


13

if you want a cheap and dirty optimized power-series expansion (the coefficients for Taylor series converge slowly) for sqrt() and a bunch of other trancendentals, i have some code from long ago. i used to sell this code, but no one has paid me for it for nearly a decade. so i think i'll release it for public consumption. this particular file was for an ...


12

I tried two approaches, naively (using only 3 segments). Surely there would be fancier methods out there. RANSAC, supposed to be a robust fitting mechanism. It's easy to stop the algorithm after a number of segments. However it may be difficult to enforce continuity between segments--as seems required in your application-- at least with a simple ...


12

What you're describing is call deconvolution. It's a concept frequently used for distorted images and for equalization in communications. As such you should be able to find a number of resources for your specific application. In general, the original image may not be recoverable exactly (it often isn't). However, you can do a pretty good job depending on ...


11

The STFT transform pair can be characterized by 4 different parameters: FFT size (N) Step size (M) Analysis window (size N) Synthesis window (size N) The process is as follows: Grab N (fft size) samples from the current input location Apply analysis window Do the FFT Do whatever you want to do in the frequency domain Inverse FFT Apply synthesis window Add ...


10

You need to either factor your FFT size into small prime factors if possible (e.g. 2, 3, 5, 7) and then use appropriate FFT butterflies (this is what FFTW does), otherwise look at padding the FFT with zeroes up to the next power of 2.


10

You need to generate early reflections with a few taps of delays (= convolution with the sum of a handful of diracs) ; and the "tail" with what is usually implemented with a network of all-pass (AP) and comb filters. The first part is trivial to implement but difficult to get to sound right. It might help to look at the positioning of peaks at the head of ...


10

The basic technique to place a mono source in stereo is called constant power panning. If you want to place a mono source at angle $\theta$ you can just use $A_\mathrm{amp}$ and $B_\mathrm{amp}$ as amplitudes for your channels: $A_\mathrm{amp} = \frac{\sqrt{2}}{2} (\cos{\theta} + \sin{\theta})$ $B_\mathrm{amp} = \frac{\sqrt{2}}{2} (\cos{\theta} - \sin{\...


9

If the "VS" is pretty much the same (save for some badge overlays as in the second example), you can use straightforward cross-correlation to detect the presence of the template in your video frame. I answered a similar question on doing this in MATLAB on Stack Overflow. You can use something like the "magic wand" tool in Photoshop to select the "VS" from ...


9

This paper discusses all of the modern exact distance transforms: "2D Euclidean distance transforms: a comparative survey", ACM Computing Surveys, Vol 40, Issue 1, Feb 2008 http://www.lems.brown.edu/~rfabbri/stuff/fabbri-EDT-survey-ACMCSurvFeb2008.pdf The paper cites the technique from Meijster, et. al. as the fastest general purpose, exact transform. This ...


9

the CPU/DSP has hardware floating point support for both single and double precision. It really depends on what kind of support you are talking about. On x86, when using the x87 style floating point instructions, you get the full 80-bit internal precision and the same processing time - whether you are working with single or double precision. But when using ...


9

IEEE float singles only provide about 24 bits of mantissa. But many DSP/filtering algorithms (IIR biquads with poles/zeros near the unit circle, etc.) require far more than 24 bits of mantissa for intermediate computational products (accumulators, etc.), just to get final results accurate to near 16 or 24 bits. For these types of algorithms, 32, 40 and 48-...


9

Thanks to the plot in Olli Niemitalo's answer I got convinced that the formula given in the book has a sign error. The non-linearity used for fuzz or distortion is always some type of smoothed clipping function, which compresses the input signal. So small input amplitudes experience little change whereas high input amplitudes are (more or less) softly ...


9

the general polynomial form is: $$\begin{align} f(u) &= \sum\limits_{n=0}^{N} \ a_n \ u^n \\ \\ &= a_{\small{0}} + \Bigg(a_{\small{1}} + \bigg(a_{\small{2}} + \Big(a_{\small{3}} + \,... \big(a_{\small{N-2}} + (a_{\small{N-1}} + a_{\small{N}} \,u \,)u \, \big)u \ ...\Big)u \, \bigg)u \, \Bigg)u\\ \end{align}$$ the latter form is using Horner's ...


9

PROLOGUE My answer to this question is in two parts since it is so long and there is a natural cleavage. This answer can be seen as the main body and the other answer as appendices. Consider it a rough draft for a future blog article. Answer 1 * Prologue (you are here) * Latest Results * Source code listing * Mathematical justification for ...


9

You mention in a comment that your target platform is a custom IC. That makes the optimization very different from trying to optimize for an already existing CPU. On a custom IC (and to a lesser extent, on an FPGA), we can take full advantage of the simplicity of bitwise operations. In addition, to reduce the area it is not only important to reduce the ...


8

Each (color) image is composed of RGB components. when you add (or reduce) a constant value to all pixels only in RED components you will see the effect equivalent to moving the RED tab towards the right, and same way reducing the RED component by a constant will have the reverse effect. Like wise you can increment/decrement each component by a fixed value ...


8

In this particular case, this would be quite difficult. The filter is a low pass with 30 dB of attenuation (mostly) but it has also two zeros on the unit circle. You can design an approximation for the inverse filter but it won't be perfect The filter is linear phase, so the inverse filter is also linear phase but non-causal. In practice this means you'll ...


8

Making a good sounding reverb is NOT easy. Feedback delay networks are definitely the way to go. The original Schroeder algorithms with all passes and comb filters suffers from "spectral thinning" which makes it metallic sounding. You need to dial in frequency dependent attenuation on the different delay lines that's representative of the reverb time (as a ...


8

essentially, in computing the naive DFT directly from the summation: $$ X[k] = \sum\limits_{n=0}^{N-1} x[n] \, e^{j 2 \pi \frac{nk}{N}} $$ there are $N$ table lookups for the twiddle factor $ e^{j 2 \pi \frac{nk}{N}} $, $N$ complex multiplications, and $N-1$ additions. and that's just for one value of $X[k]$ and one instance of $k$. then the naive DFT ...


Only top voted, non community-wiki answers of a minimum length are eligible