It all started in February this year, when when I got my Google Alerts mail for “musicbrainz picard” which included a link to this paper (“Waveprint: Efficient wavelet-based audio fingerprinting” (2007) by Shumeet Baluja and Michele Covell). I’ve never paid much attention to how audio identification systems are actually implemented, but I found it interesting that a paper published by Google researchers cited Picard, especially because Picard doesn’t implement any fingerprinting algorithm, just uses libofa. Anyway, I’ve read the paper and realized that maybe it’s not that hard to implement such a system. No tough DSP stuff or scary mathematics (of course there is some DSP stuff and mathematics, but mostly basics). The system described in the paper seemed quite straight-forward to implement, so I become curious and decided to give it a try. Later on I realized that it’s perhaps not the best system and that even the authors published new papers describing different approaches. That, combined with the fact that I was still officially an university student and had free access to all the papers from most organizations like ACM or IEEE, caused that I started reading more and more papers on the topic, learning about the history, how the systems evolved, and so on.

Many ideas were based on a paper by Yan Ke, Derek Hoiem, and Rahul Sukthankar called “Computer Vision for Music Identification” (2005). In fact, even the Last.fm fingerprinter uses the code published by the authors of this paper. This is where I learned that audio identification is more about machine learning that it is about DSP. Many useful methods for extracting interesting features from audio streams are well-known and the problem is more about how to apply and index them the best way. The basic idea here is to treat audio as a spectral image and index the content of the image. I’ll explain this in more detail and how Chromaprint uses this in a following post.

Another important paper for me was “Pairwise Boosted Audio Fingerprint” (2009) by Dalwon Jang, Chang D. Yoo, Sunil Lee, Sungwoong Kim and Ton Kalker (Ton Kalker is a co-author of a historically important paper “Robust Audio Hashing for Content Identification” (2001) published by Philips Research), which combined previous experiments of the authors with audio identification based on spectral centroid features and the indexing approach similar to the one suggested by Y. Ke, D. Hoiem and R. Sukthankar. For a long time this was the best solution I had and since it was actually not very hard to implement, the most time I spent on tweaking the configuration to get the best results.

The last major change came after I learned about “chroma” features by reading the “Efficient Index-Based Audio Matching” (2008) by Frank Kurth and Meinard Müller. I’ve read more papers about chroma features later, but this was the first and also the most important one for me and some ideas about processing the feature vectors from it are implemented in Chromaprint. Chroma features are typically used for music identification, as opposed to audio file identification, but I tried to use them with the approach I already had implemented and it nicely improved the quality of the fingerprinting function and actually reduced complexity which allowed me to use much larger training data sets.

Anyway, this is more or less how I got to this point. As I mentioned, I’ll try to describe in more detail how Chromaprint works and where are the exact ideas from in an another post later. The code is not finished yet, but the core ideas are already implemented and tested. The work that has to be done is mostly about cleaning the code, tweaking the configuration, running the learning algorithm on a better training data set (as I used only random selections of my music collection so far) and building some API that can be used by external applications.

The code is written in C++, but I plan the public API to be in plain C. Except for a FFT library (either FFTW3 or FFmpeg), it has no external dependencies. It’s released under the LGPL 2.1 license, so there should be no problem integrating it into a commercial application, assuming FFmpeg is used for FFT calculations (using FFTW3 would require the binary to be GPL compatible). The project is hosted on Launchpad using Bazaar for development. I’m sorry I didn’t include the complete development history there, but it’s just full of junk commits, so you will not miss much. :)

What I’d really like is to start actually working also on the fingerprint lookup service, for which I need as many fingerprints as possible. I have a proof of concept written in Java, using PostgreSQL and the intarray extension, which allows me to search the fingerprints using GIN indexes. This works fine on a database with tens of thousands of fingerprints, but I’m not sure if it will scale to much higher numbers. If you would like to help and you are running Debian/Ubuntu Linux, please run these commands and email me the compressed fpcollect.log file:

sudo apt-get install bzr cmake libfftw3-dev libavcodec-dev libavformat-dev libtag1-dev libboost-dev
bzr branch lp:chromaprint
cd chromaprint
cmake -DCMAKE_BUILD_TYPE=Release -DBUILD_TOOLS=ON .
make
./tools/fpcollect /path/to/your/music/library >fpcollect.log

I’m sure the recipe should be easy enough to modify for other Linux distributions. I’ll try to build a Windows binary in the next days.

UPDATE: I’ve compiled a Windows version of fpcollect. If you would like to help, please download it, change the fpcollect.bat file to point to your collection and run it. It should should produce a file called fpcollect.log like the Linux example above.

So that’s all for now. My plans for near future are to clean up the library and build some simple GUI application for collecting fingerprints. Once this is done, I can ask non-programmers to help me build a test database of fingerprints (including MusicBrainz IDs) and work primarily on the server component. There are some things that could be improved on the client library from functional point of view, but I think it’s good enough for now, so the server part seems more important at the moment.

Btw, I always considered “Chromaprint” to be a temporary name for the client library, not meant to be its final name. If you can think of a better name, ideally something that could be used also for the service/server, please let me know!

mkdir -p ~/.quodlibet/plugins/events/
cd ~/.quodlibet/plugins/events/
wget http://dl.dropbox.com/u/5215054/mbtagsubmit.py

After you enable it and let it know your MusicBrainz username and password (Music → Plugins), it will watch the songs you listen and if any of them has a “musicbrainz_trackid” and at least one “genre” tag, it will use the MusicBrainz web service to submit them. The submission normally happens only every half an hour, but if you change many files in a short time, it will submit them in batches of 20 tracks (the maximum number allowed by the web service) every 2 minutes.

CREATE TABLE "SOME_TABLE" (
    ...
    "TIMESTAMP" TIMESTAMP WITH TIME ZONE
);

Oracle is rather picky on identifier names, but since it accepted “TIMESTAMP”, I was assuming everything is fine. Later I needed to create a trigger for this table and that’s where the fun starts.

CREATE OR REPLACE TRIGGER "SOME_TABLE_TR"
BEFORE INSERT ON "SOME_TABLE"
FOR EACH ROW
BEGIN
    ...
END;

This was failing for some reason though. The only thing I got was this “nice” error message, pointing to the table name in the CREATE TRIGGER statement:

ORA-06552: PL/SQL: Compilation unit analysis terminated
ORA-06553: PLS-320: the declaration of the type of this expression is incomplete or malformed

What type? Do I have a typo somewhere? Did the table somehow get corrupted? You can’t imaging how long did it take for me to figure out that it doesn’t like the column name, which was not mentioned anywhere in the PL/SQL block. I would have no problem if it told me that I can’t use the name. There are too many restrictions on identifiers anyway. What I don’t understand is why does it allow me to create something that’s going to break other core functionality.

$ grep 'Start Here' -R ~/.local/share/tomboy/ -l
/home/lukas/.local/share/tomboy/Backup/4a47410a-4976-4cb6-8ddc-fd744710dba7.note
/home/lukas/.local/share/tomboy/7d41fff6-6cae-44bc-87b9-6486c809e7ee.note
$ gconftool-2 --set /apps/tomboy/start_note --type string 'note://tomboy/7d41fff6-6cae-44bc-87b9-6486c809e7ee'

Changes log:

• Fixed definitions of the TAGLIB_WITH_MP4 and TAGLIB_WITH_ASF macros.
• Fixed upgrading of ID3v2.3 genre frame with ID3v1 code 0 (Blues).
• New method int String::toInt(bool *ok) which can return whether the conversion to a number was successfull.
• Fixed parsing of incorrectly written lengths in ID3v2 (affects mainly compressed frames). (Bug #231075)

Change log:

• Read Vorbis Comments from the first FLAC metadata block, if there are multipe ones. (Bug #211089)
• Fixed a memory leak in FileRef’s OGA format detection.
• Fixed compilation with the Sun Studio compiler. (Bug #215225)
• Handle WM/TrackNumber attributes with DWORD content in WMA files. (Bug #218526)
• More strict check if something is a valid MP4 file. (Bug #216819)
Correctly save MP4 int-pair atoms with flags set to 0.
• Fixed compilation of the test runner on Windows.
• Store ASF attributes larger than 64k in the metadata library object.
• Ignore trailing non-data atoms when parsing MP4 covr atoms.
• Don’t upgrade ID3v2.2 frame TDA to TDRC. (Bug #228968)

1. It ignores timezones. All timestamps are treated as if they were somewhere in the US. For projects where committers live across the world (most open source projects) it’s therefore almost useless.
2. It only works for GitHub projects, obviously.

I’ve put together a little Bazaar plugin that can generate similar graphs for Bazaar branches. You can get the plugin here. It requires PyQt for image drawing, but many Bazaar users should already have PyQt installed. Once you install the plugin, you can generate a “Punchcard” by running a command like this in a branch directory:

bzr punchcard project-punchcard.png

For example, for QBzr you will get this graph:

You can see that the project is done by people who obviously have too much free time. There is activity pretty much any time. I guess only on weekend nights, people are tired and enjoy some sleep. :)

On the other hand, Picard was hacked by people with good sleep patterns over evenings and weekends:

MusicBrainz Server is in a similar situation, minus the good sleep patterns:

The last example is Bazaar. It’s mostly written by full-time employees and it shows:

This StackOverflow answer is a nice example of the problem:

$mondayStr = "last monday";
if (date('N') !== '1') {  // it's not Monday today
    $mondayStr .= " last week";
}

$monday = strtotime($mondayStr);
echo date('r', $monday);    // Mon, 22 Feb 2010 00:00:00 +1000

$sunday = $monday + 86400 * 7 - 1;
echo date('r', $sunday);    // Sun, 28 Feb 2010 23:59:59 +1000

The code seems logical. Get the timestamp of the last Monday, add 60 * 60 * 24 * 7 – 1 seconds and you have the end of Sunday. Works fine most of the time. Although, if the $monday happens to be Mon, 22 Mar 2010 00:00:00, the date that was supposed to be Sun, 28 Mar 2010 23:59:59 will actually be Mon, 29 Mar 2010 00:59:59. Why? Because 28 March 2010 has only 23 hours.

Never use timestamps to do calendar calculations. It’s hard to get it right. If you really have to, at least use GMT timestamps.

Changes since version 0.2:

• PDF export
• Support for printing
• Opening of files passed through the command line arguments (Bug #401595)
• The recently used files list now always uses absolute paths
• Implemented auto-scrolling in the diagram view (Bug #420324)
• The “Close” menu item will now only close the document, not the window (Bug #420322)
• Use the selected file format in the export dialog, instead of relying only on the extension (Bug #396056)