ID3 and audio fingerprinting
Tuesday, July 31st, 2007Today I read a brief synopsis of the ID3v2 tagging technology (ID3 tags are the embedded metadata that let your MP3 player determine the name of a song in a file, the artist, album name, etc.). I was surprised to see that ID3v2 supports the embedding of time-stamped lyrics– none of the free tagging software I saw provides a way to edit or even look at lyric data, but I did see about two commercial ones with those capabilities. Haven’t found any lyrics databases on the net, however.
I was also thinking about audio fingerprinting: since I saw a commercial advertising a cell phone that could identify a song based on a clip, I’ve been wondering how you’d go about designing such a system. One obvious thought that came to mind was using time-frequency decompositions, like wavelets, to compress the data in some way consonant with human auditory perception… but how to translate this broad idea into a specific algorithm? I chanced across libFooID, an opensource implementation of a fingerprinting algorithm; the linked page has a nice synopsis of the algorithm. This algorithm isn’t aimed on identifying songs based on arbitrary fragments, but it’s impressive and useful as is.
On a related note, some researchers at HP wrote a short report on using semantic analysis of song lyrics to identify similar music. The conclusion is that automated auditory similiarity analysis is more accurate, but the two approaches are potentially complementary. The report is worth reading just as a showcase application a probablistic version (ps) of latent semantic indexing (pdf), a technique used in automatic document indexing. Just scanning those papers on semantic analysis has given me a contact high: beautiful math concepts (like principal component analysis and relative entropy) find natural applications here.
mapping ![\phi : [0,1] \rightarrow [a,b]](/cz/latexrender/pictures/edf877565d42579f481483d94a26f926.png "\phi : [0,1] \rightarrow [a,b]")
so that all orders of derivatives vanish at 0 and 1. I’m giving it a try…
can be identified with a functional 
. It can also be identified with a vector field. 
such that 
and 
, then since the chain rule gives 
, the one-form 
is called the differential of the function 
. A one-form 
is called exact if there is some 
.
. In physics, conservative forces (fields) are exact one-forms. 
. The differential of a one-form is the two-form 
. So, if 
. One-forms such that 
is a simple region, where 
. Consequently, for closed forms, 
Applying Stoke’s theorem to the illustration below gives that 
if ![un := 1in;
o := (0,0);
z0 = o;
z1 = (1un, .5un);
z2 = (1un, 2un);
z3 = (.25un, .75un);
path p[];
label.top(btex {\Huge R} etex, (.75un, .75un));
pickup pencircle scaled 2;
p0 = z0{dir 60}..z1{right}..{dir 100}z2{dir -100};
p1 = z2{dir -100}..{dir -120}z3..{down}z0;
ahlength := 6;
drawarrow subpath (0,1) of p0;
drawarrow subpath (0,1) of p1;
draw p0;
draw p1;
label.rt(btex \Large $\gamma_1$ etex, z1 shifted (0, -.1un) );
label.lft(btex \Large $\gamma_2$ etex, z3 shifted (-.1un, 0) );](/cz/illustrender/pictures/ef6338c51082a9151826ec2c827c6ebe.png "un := 1in;
o := (0,0);
z0 = o;
z1 = (1un, .5un);
z2 = (1un, 2un);
z3 = (.25un, .75un);
path p[];
label.top(btex {\Huge R} etex, (.75un, .75un));
pickup pencircle scaled 2;
p0 = z0{dir 60}..z1{right}..{dir 100}z2{dir -100};
p1 = z2{dir -100}..{dir -120}z3..{down}z0;
ahlength := 6;
drawarrow subpath (0,1) of p0;
drawarrow subpath (0,1) of p1;
draw p0;
draw p1;
label.rt(btex \Large $\gamma_1$ etex, z1 shifted (0, -.1un) );
label.lft(btex \Large $\gamma_2$ etex, z3 shifted (-.1un, 0) );")
at 
, the center of the star, and define 
for any point 
in the domain, where 
is a path from 
and 
, and 
is connected, then 
. The idea is that if 
on 
for 
, then 
on 
, which is connected, so 
on 
, then the function 
which takes the values of 
on 
on 
on 
.
and 
is a smooth path in 
and a collection of open subsets 
of ![[t_{i-1}, t_i]](/cz/latexrender/pictures/af408963d39aa55adda77f083263cecb.png "[t_{i-1}, t_i]")
into 
. For any such choice of subdivision and open sets, if 
, 
in ![\gamma([a,b])](/cz/latexrender/pictures/0cbcd41e1115093ac7fe2240c42428f8.png "\gamma([a,b])")
, there is a neighborhood 
in which the form is exact. The preimages of these neighborhoods under ![[a,b]](/cz/latexrender/pictures/2c3d331bc98b44e71cb2aae9edadca7e.png "[a,b]")
, of which a finite subcover can be chosen. ![[t_i, t_{i+1}]](/cz/latexrender/pictures/e9e3502c6e8e268a9c1517d952b49647.png "[t_i, t_{i+1}]")
such that the image of each interval is contained in an 
be written as the differential of a function 
, then in the right half plane 
. However, the one form 
cannot be written as the differential of a function if the domain of definition is 
. What if the domain of definition is the set
?
where 
is analytic at infinity.
and coefficients 
such that 
implies 
![\sum_{n=L}^\infty \left[ u(n) - c_0 - \frac{c_1}{n} \right] = \sum_{n=L}^\infty \sum_{k=2}^\infty \frac{c_k}{n^k},](/cz/latexrender/pictures/1ee6132953ac66739171e00783258966.png "\sum_{n=L}^\infty \left[ u(n) - c_0 - \frac{c_1}{n} \right] = \sum_{n=L}^\infty \sum_{k=2}^\infty \frac{c_k}{n^k},")
; you also get the formula![\sum_{n=1}^\infty \left[ u(n) - c_0 - \frac{c_1}{n} \right] = \sum_{n=1}^{L-1} \left[ u(n) - c_0 - \frac{c_1}{n} \right] + \sum_{n=L}^\infty \sum_{k=2}^\infty \frac{c_k}{n^k}](/cz/latexrender/pictures/af939bccfed6175cd21d810d7e241cbf.png "\sum_{n=1}^\infty \left[ u(n) - c_0 - \frac{c_1}{n} \right] = \sum_{n=1}^{L-1} \left[ u(n) - c_0 - \frac{c_1}{n} \right] + \sum_{n=L}^\infty \sum_{k=2}^\infty \frac{c_k}{n^k}")
.
are real and nonnegative has a value 
given by
, 
, and 
depends on 
and 
.