This week, The Echo Nest released Echoprint – an open source music fingerprinting and identification system. A fingerprinting system like Echoprint recognizes music based only upon what the music sounds like.  It doesn’t matter what bit rate, codec or compression rate was used (up to a point) to create a music file, nor does it matter what sloppy metadata has been attached to a music file, if the music sounds the same, the music fingerprinter will recognize that.  There are a whole bunch of really interesting apps that can be created using a music fingerprinter. Among my favorite iPhone apps are Shazam and Soundhound – two fantastic over-the-air music recognition apps that let you hold your phone up to the radio and will tell you in just a few seconds what song was playing.  It is no surprise that these apps are top sellers in the iTunes app store. They are the closest thing to magic I’ve seen on my iPhone.

In addition to the super sexy applications like Shazam, music identification systems are also used for more mundane things like copyright enforcement (helping sites like Youtube keep copyright violations out of the intertubes), metadata cleanup (attaching the proper artist, album and track name to every track in a music collection), and scan & match like Apple’s soon to be released iCloud music service that uses music identification to avoid lengthy and unnecessary music uploads.  One popular use of music identification systems is to de-duplicate a music collection. Programs like tuneup will help you find and eliminate duplicate tracks in your music collection.

This week I wanted to play around with the new Echoprint system, so I decided I’d write a program that finds and reports duplicate tracks in my music collection.    Note: if you are looking to de-duplicate your music collection, but you are not a programmer, this post is *not* for you, go and get tuneup or some other de-duplicator. The primary purpose of this post is to show how Echoprint works, not to replace a commercial system.

How Echoprint works
Echoprint, like many music identification services is a multi-step process:  code generation, ingestion and lookup. In the code generation step,  musical features are extracted from audio and encoded into a string of text.  In the ingestion step, codes for all songs in a collection are generated and added to a searchable database.  In the lookup step, the codegen string is generated for an unknown bit of audio and is used as a fuzzy query to the database of previously ingested codes.  If a suitably high-scoring match is found, the info on the matching track is returned. The devil is in the details.  Generating a short high level representation of audio that is suitable for searching that is insensitive to encodings, bit rate, noise and other transformations is a challenge.  Similarly challenging is representing  a code in a way that allows for high speed querying and allows for  imperfect matching of noisy codes.

Echoprint consists of two main components: echoprint-codegen and echoprint-server.

Code Generation
echoprint-codegen is responsible for taking a bit of audio and turning it into an echoprint code.   You can grab the source from github and build the binary for your local platform.   The binary will take an audio file as input and give output a block of JSON that contains song metadata (that was found in the ID3 tags in the audio) along with a code string.  Here’s an example:

plamere$ echoprint-codegen test/unison.mp3 0 10
[
{"metadata":{"artist":"Bjork", 
    "release":"Vespertine",
     "title":"Unison",
     "genre":"", 
     "bitrate":128,"sample_rate":44100, "duration":405,
     "filename":"test/unison.mp3",
     "samples_decoded":110296,
     "given_duration":10, "start_offset":1,
     "version":4.11,
     "codegen_time":0.024046,
     "decode_time":0.641916},
     "code_count":174,
     "code":"eJyFk0uyJSEIBbcEyEeWAwj7X8JzfDvKnuTAJIojWACwGB4QeM\
       HWCw0vLHlB8IWeF6hf4PNC2QunX3inWvDCO9WsF7heGHrhvYV3qvPEu-\
       87s9ELLi_8J9VzknReEH1h-BOKRULBwyZiEulgQZZr5a6OS8tqCo00cd\
       p86ymhoxZrbtQdgUxQvX5sIlF_2gUGQUDbM_ZoC28DDkpKNCHVkKCgpd\
       OHf-wweX9adQycnWtUoDjABumQwbJOXSZNur08Ew4ra8lxnMNuveIem6\
       LVLQKsIRLAe4gbj5Uxl96RpdOQ_Noz7f5pObz3_WqvEytYVsa6P707Jz\
       j4Oa7BVgpbKX5tS_qntcB9G--1tc7ZDU1HamuDI6q07vNpQTFx22avyR", 
     "tag":0}
]

In this example, I’m only fingerprinting the first 10 second of the song to conserve space.  The code string is just a base64 encoding of a zlib compression of the original code string, which is a hex encoded series of ASCII numbers. A full version of this code is what is indexed by the lookup server for fingerprint queries.    Codegen is quite fast.  It  scans audio at roughly 250x real time per processor after decoding and resampling to 11025 Hz. This means a full song can be scanned in less than 0.5s on an average computer, and an amount of audio suitable for querying (30s) can be scanned in less than 0.04s.  Decoding from MP3 will be the bottleneck for most implementations. Decoders like mpg123 or ffmpeg can decode 30s mp3 audio to 11025 PCM in under 0.10s.

The Echoprint Server
The Echoprint server is responsible for maintaining an index of fingerprints of (potentially) millions of tracks and serving up queries.  The lookup server uses the popular Apache Solr as the search engine. When a query arrives,   the codes that have high overlap with the query code are retrieved using Solr.  The lookup server then filters through these candidates and scores them based on a number of factors such as the number of codeword matches, the order and timing of codes and so on.  If the best matching code has a  high enough score, it is considered a hit and the ID and any associated metadata is returned.

To run a server, first you ingest and index full length codes for each audio track of interest into the server index. To perform a lookup, you use echoprint-codegen to  generate a code for a subset of the file (typically 30 seconds will do) and issue that as a query to the server.

The Echo Nest hosts a lookup server, so for many use cases you won’t need to run your own lookup server. Instead , you can make queries to the Echo Nest via the song/identify call. (We also expect that many others may run public echoprint servers as well).

Creating a de-duplicator
With that quick introduction on how Echoprint works  let’s look at how we could create a de-duplicator.   The core logic is extremely simple:

       create an empty echoprint-server
       foreach mp3 in my-music-collection:
          code = echoprint-codegen(mp3)            // generate the code
          result = echoprint-server.query(code)    // look it up
          if result:                               // did we find a match?
               print 'duplicate for', mp3, 'is', result
          else:                                    // no, so ingest the code
               echoprint-server.ingest(mp3, code)

We create an empty fingerprint database.  For each song in the music collection we generate an Echoprint code and query the server for a match.  If we find one, then the mp3 is a duplicate and we report it. Otherwise, it is a new track, so we ingest the code for the new track into the echoprint server. Rinse. Repeat.

I’ve written a python program dedup.py  to do just this.  Being a cautious sort, I don’t have it actually delete duplicates, but instead, I have it just generate a report of duplicates so I can decide which one I want to keep.  The program also keeps track of its state so you can re-run it whenever you add new music to your collection.

Here’s an example of running the program:

% python dedup.py  ~/Music/iTunes

          1  1 /Users/plamere/Music/misc/ABBA/Dancing Queen.mp3
               ( lines omitted...) 
        173 41 /Users/plamere/Music/misc/Missy Higgins - Katie.mp3
        174 42 /Users/plamere/Music/misc/Missy Higgins - Night Minds.mp3
        175 43 /Users/plamere/Music/misc/Missy Higgins - Nightminds.mp3

duplicate /Users/plamere/Music/misc/Missy Higgins - Nightminds.mp3
          /Users/plamere/Music/misc/Missy Higgins - Night Minds.mp3

        176 44 /Users/plamere/Music/misc/Missy Higgins - This Is How It Goes.mp3

Dedup.py print out each mp3 as it processes it and as it finds a duplicate it reports it. It also collects a duplicate report in a file in pblml format like so:

duplicate <sep> iTunes Music/Bjork/Greatest Hits/Pagan Poetry.mp3 <sep> original <sep> misc/Bjork Radio/Bjork - Pagan Poetry.mp3
duplicate <sep> iTunes Music/Bjork/Medulla/Desired Constellation.mp3 <sep> original <sep> misc/Bjork Radio/Bjork - Desired Constellation.mp3
duplicate <sep> iTunes Music/Bjork/Selmasongs/I've Seen It All.mp3 <sep> original <sep> misc/Bjork Radio/Bjork - I've Seen It All.mp3

Again, dedup.py doesn’t actually delete any duplicates, it will just give you this nifty report of duplicates in your collection.

Trying it out

If you want to give dedup.py a try, follow these steps:

1. Download, build and install echoprint-codegen
2. Download, build, install and run the echoprint-server
3. Get dedup.py.
4. Edit line 10 in dedup.py to set the  sys.path to point at the echoprint-server API directory
5. Edit line 13 in dedup.py to set the _codegen_path to point at your echoprint-codegen executable

   % python dedup.py  ~/Music

This will find all of the dups and write them to the dedup.dat file.  It takes about 1 second per song.  To restart (this will delete your fingerprint database) run:

   % python dedup.py --restart

Note that you can actually run the dedup process without running your own echoprint-server (saving you the trouble of installing Apache-Solr, Tokyo cabinet and Tokyo cabinet).  The downside is that you won’t have any persistent server, which means that you’ll not be able to incrementally de-dup your collection – you’ll need to do it in all in one pass.   To use the local mode, just add local-True to the fp.py calls. The index is then kept in memory, no solr or Tokyo tyrant is needed.

Wrapping up
dedup.py is just one little example of the kind of application that developers will be able to create using Echoprint.  I expect to see a whole lot more in the next few months.  Before Echoprint, song identification was out of the reach of the typical music application developer, it was just too expensive.  Now with Echoprint, anyone can incorporate music identification technology into their apps.  The result will be fewer headaches for developers and much  better music applications for everyone.