# How would you compute that “average” ?

I created a DJ-ing application that allows you to mix your MP3s with a real turntable. So I generated an audio timecode to burn on a CD, left channel is the absolute position, right channel is a synchronization sine which frequency is 2205 Hz. Left channel is same frequency except that it represents binary sequences.

Precision is an absolute pre-requisite, the pitch on my Pioneer CDJ-1000 has a precision of 0.02% which is good enough to properly beatmatch songs. I have no problem on getting the absolute position but with the right channel. After some searching, I found the Zero Crossing Rate algorithm to try detect the pitch. When I process data in real-time however, the pitch moves constantly.

After some searching I found out that as samples are discrete values, so not continuous if I'm right, there's not enough precision with a sample rate of 44100 Hz. Period of 20 samples is 2205 Hz, period of 21 samples is 2100 Hz; so the problem needs something more high-level.

I found then harmonic average, and moving average, results are somewhat more stable. FFT is the best but costs a lot of CPU, using a size of 65536 and time to compute it, whereas with the zero-crossing rate, I can update the value very frequently. The latest candidate, I still need to test is the Standard Deviation.

There must be some math formula that helps for that particular problem, but as I know not much about maths, I am somewhat lost.

Do you have any ideas ?

Thanks a lot :-)))

-
Not appropriate for MO. Might be salvageable if it could be recast as something like (e.g.) a question about the Shannon sampling theorem. – Steve Huntsman Jan 28 '10 at 4:06
Could you elaborate on what you are trying to accomplish? What is the input, and what should the output be? – Douglas Zare Jan 28 '10 at 4:09
What you're doing sounds very cool. Unfortunately (well, not really) Math Overflow is not the repository for all cool, math-related things. I think you'll have more luck on another site. – Pete L. Clark Jan 28 '10 at 4:43
There's a thread on meta, tea.mathoverflow.net/discussion/185/elitism-for-elitisms-sake prompted by this question that may be of interest. – Scott Morrison Jan 28 '10 at 5:46
I was persuaded by the discussion on meta and have voted to reopen. Apologies for the waffling. – Pete L. Clark Jan 28 '10 at 18:59

It sounds to me that you need to detect the tempo of the music, and not the pitch. If you are trying to use a pitch-detection algorithms, then these are going to fluctuate rapidly, as they will lock onto the high frequences in your music. It sounds like you need something that filters out all but the lowest frequencies and allows you to determine how many BPM (beat per minute) the music is, as well as the phase of the beat also, so that you can do beatmatching as you originally mention.

However, I don't think that anyone here is going to be able to give you a simple formula for doing this directly from the samples. Digital signal processing is, by its very nature, a fairly mathematical subject. I do think that if you try Googling for "beat-matching signal-processing", or "beat-matching matlab", you will be pointed in the right direction, as you might find a published algorithm for doing exactly what you need. For instance, I found the following paper by searching: Design of an Automatic Beat-Matching Algorithm for Portable Media Devices. It might be worth looking at if you can get it without paying, say through a university with a subscription. Otherwise, I'm sure there are 100's of similar papers you can find on this subject. Also, many universities teach an audio signal processing class, and often the notes from these classes are online. Beat-matching is a common project for students to try in such classes and I'm sure you will be able to find some examples where people have done it.

Sorry I couldn't give you more explicit advice, but I hope I understood your question correctly and have pointed you in the right direction. Good luck.

-
Another source would be to go to the Journal of Mathematics and Music, look up the editorial board and the authors, and use their names to refine your search. The journal link: tandf.co.uk/journals/journal.asp?issn=1745-9737&linktype=5 A paper on beat matching that pops up: W. A. Sethares, R. D. Morris and J. C. Sethares, "Beat tracking of audio signals using low level audio features," IEEE Trans. On Speech and Audio Processing, Vol. 13, No. 2, March 2005. You can find the .pdf on Sethares's webpage, although I'm not sure how relevant it is for your situation. – Ryan Budney Jan 28 '10 at 14:59

I'm chanelling a response from an electrical engineer friend who works in a related area:

The thing he's trying to do is to match the beats and you can't just use zero crossing algorithms or "averages"... The code from the the Sethares paper mentioned (above) works pretty well, but it's in matlab, which means that it doesn't work in real time (because matlab has no real-time processing capabilities, not because the algorithm is inherently noncausal). So I'm doubtful whether it would be of any immediate use to the questioner.

There are some commercial products that are starting to appear, which mostly work by assuming that there is a steady drum beat underlying the music (this makes the problem a lot easier -- for instance, if you know there is a bass drum that regularly hits on 1 and 3, you can synchronize to it). So here it would depend on what style of music he is working with.

From his response it sounds like if you're sticking to something like electronic dance music then there are readily-available commercial products (I find some by googling). But if you're trying to automate beat-matching of Indonesian gamelan music to an acoustic guitar solo, you'd have more troubles.

edit: The Sethares paper provides routines but it also provides a reference to the beat-tracking literature. If your main interest is to have a convienient way to beat-track, it would seem like the best thing to do would be to avoid real-time computations. Precompute the relevant data using an algorithm like the ones Sethares (and all) propose. Store that information beside your music so that you'd have all the information available and not need any further computations or fancy hardware.

-
In my experience, adding a DSP chip or so is not going to increase the cost by much. However one would need to know how to program it. – Anweshi Jan 30 '10 at 23:41