Skip to content
This repository

HTTPS clone URL

Subversion checkout URL

You can clone with HTTPS or Subversion.

Download ZIP
branch: master
Fetching contributors…

Octocat-spinner-32-eaf2f5

Cannot retrieve contributors at this time

file 300 lines (151 sloc) 9.76 kb
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en"><head>

    <meta http-equiv="Content-Type" content="text/html;charset=utf-8">

    <meta name="generator" content="Plone - http://plone.org">

    <!-- Internet Explorer fix, forces IE8 into newest possible rendering
engine even if it's on an intranet. This has to be defined before any
script/style tags. -->
    <meta http-equiv="X-UA-Compatible" content="IE=edge">

    
      <base href="http://oldzope.rudd-o.com/Rudd-O.com/new-projects/python-audioprocessing/documentation/manuals/algorithms/butterscotch-signatures"><!--[if lt IE 7]></base><![endif]-->
    

    <title>Butterscotch signatures — Rudd-O.com</title>

  
  
    
    
    
    
  


  
  
    
    
    <meta content="Here's all the information you need to know about Butterscotch." name="DC.description">
    <meta content="Here's all the information you need to know about Butterscotch." name="description">
    <meta content="text/html" name="DC.format">
    <meta content="Page" name="DC.type">
    <meta content="RuddO" name="DC.creator">
    <meta content="2008-12-04 12:10:28" name="DC.date.modified">
    <meta content="2008-12-04 11:54:11" name="DC.date.created">
    <meta content="en" name="DC.language">

    

    <link rel="shortcut icon" type="image/x-icon" href="http://oldzope.rudd-o.com/Rudd-O.com/favicon.ico">



    <link rel="home" href="http://oldzope.rudd-o.com/Rudd-O.com" title="Front page">

    <link rel="contents" href="http://oldzope.rudd-o.com/Rudd-O.com/sitemap" title="Site Map">






    <link rel="search" href="http://oldzope.rudd-o.com/Rudd-O.com/search_form" title="Search this site">



    <!-- Disable IE6 image toolbar -->
    <meta http-equiv="imagetoolbar" content="no">
    
    
    

    
    

    
    

    
    

  </head>

  <body class="section-new-projects template-referencemanualpage_view" dir="ltr">
    <div id="visual-portal-wrapper">

      

      

      <table id="portal-columns">
        <tbody>
          <tr>
            
            
            

            
            <td id="portal-column-content">

              
                <div class="">

                  


                  <div id="region-content" class="documentContent">

                    
                    
                    
                    

                    

    


                    
                    

                    
                    <div id="content">
                      
                      <div>
                   
    
        
    <h1 class="documentFirstHeading">
        <img src="http://oldzope.rudd-o.com/Rudd-O.com/referencemanual_icon.gif" alt="" title="Reference manual" height="16" width="16">
        1.
        Butterscotch signatures
    </h1>
    
    <a href="http://oldzope.rudd-o.com/Rudd-O.com/new-projects/python-audioprocessing/documentation/manuals/algorithms" class="link-parent">
        Up one level
        </a>

    <div class="jumpBox">

    <form method="get" action="http://oldzope.rudd-o.com/Rudd-O.com/new-projects/python-audioprocessing/documentation/manuals/algorithms/butterscotch-signatures">
        <label for="destination" class="hiddenStructure">Jump to: </label>
        <select name=":action" onchange="window.location.href=this.options[this.selectedIndex].value">
<option value="referencemanual-all-pages" title="Useful for printing, presentation mode etc.">
All content on one page
</option>
            <option selected="selected" value="http://oldzope.rudd-o.com/Rudd-O.com/new-projects/python-audioprocessing/documentation/manuals/algorithms/butterscotch-signatures">
                1.
                Butterscotch signatures
            </option>
        </select>
        <noscript>
            &lt;input class="standalone" type="submit"
                   value="Ir" /&gt;
        </noscript>
    </form>
</div>

    <div class="documentDescription">Here's all the information you need to know about Butterscotch.</div>
    
    
    
    
<p>
A Butterscotch signature consists of at most 30 spectrum analyses, each
performed on consecutive 4-second blocks of audio, starting from the
onset of the first 5 dB RMS increase counted computed from 22-sample
blocks (when using a 44.100 Hz sampling rate).</p>
<p>Each spectrum analysis reduces each 4-second audio block to 256
equal-width frequency bands (using a 512-point FFT), then cuts the high
half of the bands, and finally averages the remaining 128 bands
logarithmically, to result in 8 log bands from the first significant
band to 11.025 KHz (the center of the highest frequency band is around
8.4 KHz). Each sample represents the relative signal amplitude, with
the reference 0 dB amplitude being equivalent to the value 1.0. Samples
in the spectrum analysis are not normalized to dB, but instead left
raw. Chunks supplied to the FFT are windowed by a Hann window.</p>
<p>As it turns out, the average of the correlation coefficient between
corresponding bands (across the time domain) among a set of songs is
surprisingly effective. Identical (non-rolling-start) songs correlate
almost perfectly regardless of start time differences, encoding bitrate
or even incompleteness. In contrast, different versions of the same
song and different songs correlate very weakly or negatively.
Additionally, the fingerprint has a very useful quality control purpose
too, as you will see graphically below.</p>
<p>
This is a graphical representation output of a spectrum in time -- not a Butterscotch fingerprint, but you get the idea:</p>
<p align="center"><img class="image-inline" src="Spectrumintime.png" alt="Spectrum in time"></p>
<p align="left">Butterscotch itself does not work with dB-adjusted values, but the suite can be used to perform spectrum analysis in decibels, in linear
(equal-width) bands and up to full-spectrum (22 KHz), for spectrum
plots:</p>
<p align="center"><img class="image-inline" src="SpectrumintimedBadjusted.png" alt="Spectrum in time (dB-adjusted)"></p>
<p>
Additionally, the suite can quantize these decibel-based points to a
character, and display a character-based table onscreen, in a sort of
very coarse, horizontal spectrogram.</p>
<h3 id="Propertiesofthealgorithm">Properties of the algorithm<span class="link-external"><a title="Link to this section" class="anchor" href="http://projects.rudd-o.com/python-audioprocessing/wiki/ButterScotch#Propertiesofthealgorithm"></a></span></h3>
<p>
The algorithm's requirements specify that the algorithm:</p>
<ul><li>Be robust against different "onsets of audible signal". If two
different files contain the same song, and one of them has some extra
silence at the start, that's not a problem.
</li><li>Be robust against identifying songs with rolling starts. A
song in a megamix is not conflated with the same song's album / single
release.
</li><li>Be robust against lossy compression. The 16~18 KHz lowpass
algorithm in MP3 does not affect Butterscotch. A song encoded twice
with different quality settings is reliably identified as the same
song.
</li><li>Be robust against incomplete songs. Two copies of the same
song (one complete, one incomplete) still correlate highly, and you can
use your music player to weed out the shorter one.
</li><li>Be fast. A 20.000 song collection needs to be fingerprinted
efficiently, and posterior analysis of the collection needs to be
nearly instantaneous. Oops... we're working on that.
</li></ul>
<p>
To accomplish these, the algorithm:</p>
<ul><li>vectorizes all operations as much as possible,
</li><li>discards frequencies above 11 KHz,
</li><li>seeks to onset of audio by identifying the first RMS rise in a very short time frame,
</li><li>does not perform FFTs until end of audio, but just for two minutes.
</li></ul>
<p>The drawback of the algorithm is that it requires an
explosive (quadratic time) amount of correlations. Finding tracks
similar to one song is an O(N) operation. However, correlations can be
computed incredibly quickly (less than a millisecond for a pair of
signatures) and cached for future on demand use, so for collections
below 50000 tracks it's not a problem.</p>
<h3 id="Howwegeneratethesignatures">How we generate the signatures<span class="link-external"><a title="Link to this section" class="anchor" href="http://projects.rudd-o.com/python-audioprocessing/wiki/ButterScotch#Howwegeneratethesignatures"></a></span></h3>
<ul><li>Seek to the onset of audio as described above
</li><li>Generate 30 real FFTs (rfft) for each 4-second-long block
</li><li>Discard the DC component of the rfft
</li><li>Discard the highs half of the remainder (the library does not do this by default, but the command line tools do)
</li><li>Log-average the remaining bands
</li><li>Return a two-dimensional array
</li></ul>
<p>
This makes it easy to perform frequency- and time-based correlations on the signatures.</p>
<h3 id="Andwhataboutthename">And what about the name?<span class="link-external"><a title="Link to this section" class="anchor" href="http://projects.rudd-o.com/python-audioprocessing/wiki/ButterScotch#Andwhataboutthename"></a></span></h3>
<p>
It's just a Googleable name. Get over it.</p>
<p align="left">&nbsp;</p>

      

    

    


</div>
                    </div>
                    

                    
                    
                      
    




                    
                    

                    
                    

                  </div>

                </div>

              
            </td>
            

            
            
            
          </tr>
        </tbody>
      </table>
      

      
      
      

      

        

  




      

      
    </div>




</body></html>
Something went wrong with that request. Please try again.