# Tag Info

## Hot answers tagged algorithms

30

I was in the middle of typing an answer pretty much exactly like Yoda's. He's is probably the most reliable but, I'll proposed a different solution so you have some options. If you take a histogram of your signal, you will more than likely a bell or triangle like shape depending on the signal type. Clean signals will tend to follow this pattern. Many ...

29

There are lots of edge detection possibilities, but the 3 examples you mention happen to fall in 3 distinct categories. Sobel This approximates a first order derivative. Gives extrema at the gradient positions, 0 where no gradient is present. In 1D, it is = $\left[ \begin{array}{ccc} -1 & 0 & 1 \end{array} \right]$ smooth edge => local minimum or ...

23

The idea of autocorrelation is to provide a measure of similarity between a signal and itself at a given lag. There are several ways to approach it, but for the purposes of pitch/tempo detection, you can think of it as a search procedure. In other words, you step through the signal sample-by-sample and perform a correlation between your reference window ...

20

The simplest answer if you're dealing with short recordings is to listen to it and detect "pops" (short spiked sound) in the playback. However, a more robust solution is to analyze the frequency spectrum of the recording. Recall that when a signal gets clipped at some threshold, it locally resembles a square wave in the clipped regions. This introduces ...

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 While Sobel and Laplacian are simply filters, Canny goes further than that in two ways. First, it does non-maximum suppression which gets rid of noise produced by all sorts of objects and color gradients in an image. Secondly, it actually includes a step that allows you to discern between different edge directions and to fill missing points of a line. In ... 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 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 ... 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

Pedro F. Felzenszwalb and Daniel P. Huttenlocher have published their implementation for the distance transform. You cannot use it for volumetric images, but maybe you can extend it to support 3d data. I have only used it as a black box.

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 ...

14

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 ...

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

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

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 ...

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

I think the distinction you're looking for is more like empirical vs. theoretical (as opposed to supervised vs. unsupervised), but I could be wrong about that. In other words, the ideal thing would be to have a theoretical definition of various genres, rather than just a bunch of opaque data which can be used to classify a song [without any real ...

10

This can be accomplished with a convolution of the distance transform. Use a distance transform on the edge of the mask. Then threshold this distance transform to remove values beyond some distance. I think the secret to getting the shading is to convolve the distance transform result with a kernel that looks something like this: [ -1.0 -1.0 -1.0 -1.0 ...

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 ...

9

A bit of this depends on the method of record. It sounds like you are using only 1 convertor, which simplifies things somewhat. You should look for anything above some threshold, and specifically for more than one point next to each other. Typically, A/D convertors don't actually read to their max value unless you test it very exactly, so realize that the ...

9

The two most important decisions when trying to detect edges are, to me usually: Can I segment the objects instead, and then use a morphological operator to find the edge of the binary (segmented) image? With noisy data, this tends to be more robust. What edge-preserving smoothing filter should I use to reduce image noise? Edge filters are based on ...

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

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

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 ...

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