{
 "metadata": {
  "name": "",
  "signature": "sha256:a95e890d187878bc772c53a63e8c02e8216cb324385f7ceea42dd2997dcc4d5d"
 },
 "nbformat": 3,
 "nbformat_minor": 0,
 "worksheets": [
  {
   "cells": [
    {
     "cell_type": "heading",
     "level": 1,
     "metadata": {},
     "source": [
      "Music Fingerprinting using Locality Sensitive Hashing"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "This notebook shows a simple system for performing retrieval of musical tracks using LSH."
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Import libraries:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "import librosa\n",
      "import os\n",
      "import os.path"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 26
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Set figure size:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "rcParams['figure.figsize'] = (15, 5)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 27
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Select training data:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "training_dir = '../train/'\n",
      "training_files = [os.path.join(training_dir, f) for f in os.listdir(training_dir)]"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 28
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Define a hash function:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def hash_func(vecs, projections):\n",
      "    bools = dot(vecs, projections.T) > 0\n",
      "    return [bool2int(bool_vec) for bool_vec in bools]"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 29
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def bool2int(x):\n",
      "    y = 0\n",
      "    for i,j in enumerate(x):\n",
      "        if j: y += 1<<i\n",
      "    return y"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 30
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "bool2int([False, True, False, True])"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 31,
       "text": [
        "10"
       ]
      }
     ],
     "prompt_number": 31
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "X = randn(10,100)\n",
      "P = randn(3,100)\n",
      "hash_func(X, P)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 32,
       "text": [
        "[6, 7, 4, 6, 3, 0, 0, 4, 0, 3]"
       ]
      }
     ],
     "prompt_number": 32
    },
    {
     "cell_type": "heading",
     "level": 3,
     "metadata": {},
     "source": [
      "Create three LSH structures: Table, LSH, and MusicSearch:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "class Table:\n",
      "    \n",
      "    def __init__(self, hash_size, dim):\n",
      "        self.table = dict()\n",
      "        self.hash_size = hash_size\n",
      "        self.projections = randn(self.hash_size, dim)\n",
      "\n",
      "    def add(self, vecs, label):\n",
      "        entry = {'label': label}\n",
      "        hashes = hash_func(vecs, self.projections)\n",
      "        for h in hashes:\n",
      "            if self.table.has_key(h):\n",
      "                self.table[h].append(entry)\n",
      "            else:\n",
      "                self.table[h] = [entry]\n",
      "\n",
      "    def query(self, vecs):\n",
      "        hashes = hash_func(vecs, self.projections)\n",
      "        results = list()\n",
      "        for h in hashes:\n",
      "            if self.table.has_key(h):\n",
      "                results.extend(self.table[h])\n",
      "        return results"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 33
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "class LSH:\n",
      "    \n",
      "    def __init__(self, dim):\n",
      "        self.num_tables = 4\n",
      "        self.hash_size = 8\n",
      "        self.tables = list()\n",
      "        for i in range(self.num_tables):\n",
      "            self.tables.append(Table(self.hash_size, dim))\n",
      "    \n",
      "    def add(self, vecs, label):\n",
      "        for table in self.tables:\n",
      "            table.add(vecs, label)\n",
      "    \n",
      "    def query(self, vecs):\n",
      "        results = list()\n",
      "        for table in self.tables:\n",
      "            results.extend(table.query(vecs))\n",
      "        return results\n",
      "\n",
      "    def describe(self):\n",
      "        for table in self.tables:\n",
      "            print table.table"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 34
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "class MusicSearch:\n",
      "    \n",
      "    def __init__(self, training_files):\n",
      "        self.frame_size = 4096\n",
      "        self.hop_size = 4000\n",
      "        self.fv_size = 12\n",
      "        self.lsh = LSH(self.fv_size)\n",
      "        self.training_files = training_files\n",
      "        self.num_features_in_file = dict()\n",
      "        for f in self.training_files:\n",
      "            self.num_features_in_file[f] = 0\n",
      "                \n",
      "    def train(self):\n",
      "        for filepath in self.training_files:\n",
      "            x, fs = librosa.load(filepath)\n",
      "            features = librosa.feature.chromagram(x, fs, n_fft=self.frame_size, hop_length=self.hop_size).T\n",
      "            self.lsh.add(features, filepath)\n",
      "            self.num_features_in_file[filepath] += len(features)\n",
      "                \n",
      "    def query(self, filepath):\n",
      "        x, fs = librosa.load(filepath)\n",
      "        features = librosa.feature.chromagram(x, fs, n_fft=self.frame_size, hop_length=self.hop_size).T\n",
      "        results = self.lsh.query(features)\n",
      "        print 'num results', len(results)\n",
      "\n",
      "        counts = dict()\n",
      "        for r in results:\n",
      "            if counts.has_key(r['label']):\n",
      "                counts[r['label']] += 1\n",
      "            else:\n",
      "                counts[r['label']] = 1\n",
      "        for k in counts:\n",
      "            counts[k] = float(counts[k])/self.num_features_in_file[k]\n",
      "        return counts\n"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 35
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Train:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "ms = MusicSearch(training_files)\n",
      "ms.train()"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 36
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Test:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "test_file = '../test/brennan03.wav'\n",
      "results = ms.query(test_file)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "num results 171464\n"
       ]
      }
     ],
     "prompt_number": 39
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Display the results:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "for r in sorted(results, key=results.get, reverse=True):\n",
      "    print r, results[r]"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "../train/lady_madonna_crop.wav 64.2857142857\n",
        "../train/lady_madonna.wav 62.9397590361\n",
        "../train/brandenburg3_01.wav 57.91\n",
        "../train/brahms_s1_1_perlman_02.wav 50.6964285714\n",
        "../train/dont_stop_believin.wav 46.626984127\n",
        "../train/konstantine.wav 45.0076335878\n",
        "../train/Beethoven_vln_sonata5_Francescatti_01.wav 43.7115384615\n",
        "../train/office_theme.wav 42.8313253012\n",
        "../train/brahms_s1_1_perlman_03.wav 42.0535714286\n",
        "../train/bach_s3_3_szeryng_01.wav 41.8928571429\n",
        "../train/bach_p3_1_heifetz_01.wav 40.125\n",
        "../train/Beethoven_vln_sonata5_Zukerman_01.wav 40.0377358491\n",
        "../train/bach_p3_1_perlman_01.wav 39.6964285714\n",
        "../train/brahms_s1_1_perlman_05.wav 37.6785714286\n",
        "../train/brahms_s1_1_perlman_04.wav 37.4107142857\n",
        "../train/brahms_rhapsody_02.wav 37.2\n",
        "../train/Bach Vln Partita3 - Milstein 1955 - 03.wav 37.1609195402\n",
        "../train/brahms_rhapsody_01.wav 36.578313253\n",
        "../train/Beethoven_vln_sonata5_Zukerman_04.wav 36.0344827586\n",
        "../train/bach_s3_3_szeryng_05.wav 35.8214285714\n",
        "../train/bach_p3_1_heifetz_04.wav 34.3392857143\n",
        "../train/Beethoven_vln_sonata5_Zukerman_02.wav 33.8208955224\n",
        "../train/bach_p3_1_heifetz_02.wav 33.2321428571\n",
        "../train/Beethoven_vln_sonata5_Francescatti_05.wav 33.0862068966\n",
        "../train/bach_p3_1_heifetz_05.wav 32.8928571429\n",
        "../train/Bach Vln Partita3 - Fischbach 2004 - 03.wav 32.6033519553\n",
        "../train/Beethoven_vln_sonata5_Oistrakh_01.wav 32.4561403509\n",
        "../train/Beethoven_vln_sonata5_Francescatti_02.wav 31.546875\n",
        "../train/Beethoven_vln_sonata5_Oistrakh_04.wav 31.3928571429\n",
        "../train/Beethoven_vln_sonata5_Francescatti_03.wav 31.0\n",
        "../train/Beethoven_vln_sonata5_Zukerman_03.wav 30.4166666667\n",
        "../train/moonlight.wav 30.36\n",
        "../train/Beethoven_vln_sonata5_Francescatti_04.wav 29.641509434\n",
        "../train/bach_s3_3_szeryng_02.wav 29.0892857143\n",
        "../train/Bach Vln Partita3 - Milstein 1955 - 01.wav 28.8102564103\n",
        "../train/Bach Vln Partita3 - Fischbach 2004 - 01.wav 28.6977777778\n",
        "../train/bach_p3_1_perlman_02.wav 28.4285714286\n",
        "../train/Beethoven_vln_sonata5_Oistrakh_05.wav 28.3181818182\n",
        "../train/Beethoven_vln_sonata5_Zukerman_05.wav 26.6666666667\n",
        "../train/bach_s3_3_szeryng_04.wav 26.5535714286\n",
        "../train/Beethoven_vln_sonata5_Oistrakh_02.wav 26.4444444444\n",
        "../train/bach_p3_1_perlman_05.wav 26.4107142857\n",
        "../train/bach_p3_1_perlman_06.wav 26.0\n",
        "../train/bach_p3_1_perlman_04.wav 25.6428571429\n",
        "../train/bach_p3_1_heifetz_03.wav 25.3928571429\n",
        "../train/bach_p3_1_perlman_03.wav 24.9464285714\n",
        "../train/brahms_s1_1_perlman_01.wav 24.6785714286\n",
        "../train/bach_s3_3_szeryng_03.wav 23.7678571429\n",
        "../train/bach_s3_3_szeryng_06.wav 23.5178571429\n",
        "../train/Bach Vln Sonata1 - Fischbach 2004 - 02.wav 23.4891774892\n",
        "../train/Beethoven_vln_sonata5_Oistrakh_03.wav 23.0909090909\n",
        "../train/Bach Vln Sonata1 - Milstein 1954 - 02.wav 22.6527777778\n",
        "../train/brahms_s1_1_perlman_06.wav 17.8035714286\n"
       ]
      }
     ],
     "prompt_number": 40
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 38
    }
   ],
   "metadata": {}
  }
 ]
}