4 ms·

A more interesting story is behind the blog post linked in the article to someone else's implementation (which I also think contains a bit more detail than this

by elteto 4y ago

A more interesting story is behind the blog post linked in the article to someone else's implementation (which I also think contains a bit more detail than this one): [0] https://www.royvanrijn.com/blog/2010/06/creating-shazam-in-java/ https://www.royvanrijn.com/blog/2010/06/creating-shazam-in-j... [1] https://www.royvanrijn.com/blog/2010/06/music-matching-part-deux/ https://www.royvanrijn.com/blog/2010/06/music-matching-part-... Turns out he was contacted and threatened by some patent lawyers from Shazam for writing the above blog posts: [2] https://www.royvanrijn.com/blog/2010/07/patent-infringement/ https://www.royvanrijn.com/blog/2010/07/patent-infringement/ [3] https://www.royvanrijn.com/blog/2010/07/patent-publicity/ https://www.royvanrijn.com/blog/2010/07/patent-publicity/ [4] https://www.royvanrijn.com/blog/2010/11/patent-infrigement-part-2/ https://www.royvanrijn.com/blog/2010/11/patent-infrigement-p... And of course, the original HN post: [5] https://news.ycombinator.com/item?id=1496683 https://news.ycombinator.com/item?id=1496683 It seems he eventually just told them to go pound sound (!!). Good for him!

tails4e 4y ago
This was all making sense until the hashing part. To me it seemed that a slight change in recorded volume would change the magnitude and as a result the hash. Perhaps noramization over the recorded sample would help, but didn't see that. Still, I'm surprised the hash is so simple and still works.
- triggercut 4y ago
  Around the time ML/AI was starting to take off again, (I want to say 2011/2012 ish) I was doing research into applying OCR methods to recognise engineering symbols on drawings (both hand-drawn as a graphical rep and CAD as a vector rep). OCR uses locally-sensitive-hashing techniques, where minute changes, like a couple of pixels difference here and there, in theory result in similar hashes. What you really need to do is look at your windowing and overlaps and tune those to get something that actually gives you localities that are useful. This worked quite well for me. After running a "training-set" of sorts I created a small tool that ran over a quarter-million engineering drawings to get counts of each symbol from the set. (I'm going to hand-wave some implementation complexity here but essentially) If an exact match couldn't be found, the item being searched would show with thumbnails of it's nearest neighbours off to the side, you could select if it was essentially the same as one of those. (Sort of like "is this, this person" in Google Photos and the Apple equivalent) The next step after this POC was to expand to discover symbols used most next to other symbols to use as contextual menu items in other CAD software to speed up drawing production, since a lot of time was spent placing a symbol, then stopping to text search the item you were placing next. Unfortunately I was retrenched soon after and didn't get to progress. A couple of years later I took this a dimension further and was prepping for a PHD that would look at this for 3D-objects and models using naively generated voxel representations. Almost by accident I found group at/backed-by DARPA had a patent pending on a similar method. In retrospect I should have just gone all in on a photogrammetry based method since that kind of won out as a superior method - but it was still early days. The moral of the story is that everything is pattern recognition and simple methods from before this last decade of ML/AI could do some cool stuff too.
  - deleted 4y ago
    [deleted]
- a-dub 4y ago
  that's basically what it does, it finds peaks relative to total power. you can think of it as like identifying continents by constellations of mountain tops which is robust to whatever chaos might be happening at sea level.
chestervonwinch 4y ago
The patent: https://patents.google.com/patent/US6990453 https://patents.google.com/patent/US6990453
- krzyk 4y ago
  I wonder if they have such pattern in EU or Netherlands. US tends to patent stuff that wouldn't fly in Europe.
  - easytiger 4y ago
    It's more complicated[1] that but essentially there are no software patents in EU or Europe. Sadly the EU Commission have been trying to get them into legislation for over a decade[2]. It's fits perfectly with their highly protectionist authoritarian centralised control and regulation agenda. Having worked in companies it's immaterial anyway as big companies with a USA based vehicle will still be patent trolled if they do business there. Seen it happen [1] https://en.m.wikipedia.org/wiki/Software_patents_under_the_European_Patent_Convention https://en.m.wikipedia.org/wiki/Software_patents_under_the_E... [2] http://www.europarl.europa.eu/sides/getDoc.do?pubRef=-//EP//NONSGML+IM-PRESS+20050819FCS01001+0+DOC+PDF+V0//EN&language=EN http://www.europarl.europa.eu/sides/getDoc.do?pubRef=-//EP//...
dang 4y ago
Ok, we've changed to that (first) link from https://www.toptal.com/algorithms/shazam-it-music-processing-fingerprinting-and-recognition https://www.toptal.com/algorithms/shazam-it-music-processing.... Thanks! Related: Patent infringement claim re: “Creating Shazam in Java” blogpost (2010) - https://news.ycombinator.com/item?id=9594480 https://news.ycombinator.com/item?id=9594480 - May 2015 (18 comments) Source code example of the Shazam algorithm - https://news.ycombinator.com/item?id=5724442 https://news.ycombinator.com/item?id=5724442 - May 2013 (16 comments) Creating Shazam in Java - https://news.ycombinator.com/item?id=5723863 https://news.ycombinator.com/item?id=5723863 - May 2013 (42 comments) Implementing Shazam with Java in a weekend - https://news.ycombinator.com/item?id=1702975 https://news.ycombinator.com/item?id=1702975 - Sept 2010 (22 comments) Told to remove blog posts describing patented algorithm - https://news.ycombinator.com/item?id=1496683 https://news.ycombinator.com/item?id=1496683 - July 2010 (147 comments)
rezic 4y ago
The patent infringement part 2 update was in 2010. Wonder if they ever got back to him.

by elteto 4y ago

tails4e 4y ago

This was all making sense until the hashing part. To me it seemed that a slight change in recorded volume would change the magnitude and as a result the hash. Perhaps noramization over the recorded sample would help, but didn't see that. Still, I'm surprised the hash is so simple and still works.

triggercut 4y ago
Around the time ML/AI was starting to take off again, (I want to say 2011/2012 ish) I was doing research into applying OCR methods to recognise engineering symbols on drawings (both hand-drawn as a graphical rep and CAD as a vector rep). OCR uses locally-sensitive-hashing techniques, where minute changes, like a couple of pixels difference here and there, in theory result in similar hashes. What you really need to do is look at your windowing and overlaps and tune those to get something that actually gives you localities that are useful. This worked quite well for me. After running a "training-set" of sorts I created a small tool that ran over a quarter-million engineering drawings to get counts of each symbol from the set. (I'm going to hand-wave some implementation complexity here but essentially) If an exact match couldn't be found, the item being searched would show with thumbnails of it's nearest neighbours off to the side, you could select if it was essentially the same as one of those. (Sort of like "is this, this person" in Google Photos and the Apple equivalent) The next step after this POC was to expand to discover symbols used most next to other symbols to use as contextual menu items in other CAD software to speed up drawing production, since a lot of time was spent placing a symbol, then stopping to text search the item you were placing next. Unfortunately I was retrenched soon after and didn't get to progress. A couple of years later I took this a dimension further and was prepping for a PHD that would look at this for 3D-objects and models using naively generated voxel representations. Almost by accident I found group at/backed-by DARPA had a patent pending on a similar method. In retrospect I should have just gone all in on a photogrammetry based method since that kind of won out as a superior method - but it was still early days. The moral of the story is that everything is pattern recognition and simple methods from before this last decade of ML/AI could do some cool stuff too.
- deleted 4y ago
  [deleted]
a-dub 4y ago
that's basically what it does, it finds peaks relative to total power. you can think of it as like identifying continents by constellations of mountain tops which is robust to whatever chaos might be happening at sea level.

chestervonwinch 4y ago

The patent: https://patents.google.com/patent/US6990453 https://patents.google.com/patent/US6990453

krzyk 4y ago
I wonder if they have such pattern in EU or Netherlands. US tends to patent stuff that wouldn't fly in Europe.
- easytiger 4y ago
  It's more complicated[1] that but essentially there are no software patents in EU or Europe. Sadly the EU Commission have been trying to get them into legislation for over a decade[2]. It's fits perfectly with their highly protectionist authoritarian centralised control and regulation agenda. Having worked in companies it's immaterial anyway as big companies with a USA based vehicle will still be patent trolled if they do business there. Seen it happen [1] https://en.m.wikipedia.org/wiki/Software_patents_under_the_European_Patent_Convention https://en.m.wikipedia.org/wiki/Software_patents_under_the_E... [2] http://www.europarl.europa.eu/sides/getDoc.do?pubRef=-//EP//NONSGML+IM-PRESS+20050819FCS01001+0+DOC+PDF+V0//EN&language=EN http://www.europarl.europa.eu/sides/getDoc.do?pubRef=-//EP//...

dang 4y ago

Ok, we've changed to that (first) link from https://www.toptal.com/algorithms/shazam-it-music-processing-fingerprinting-and-recognition https://www.toptal.com/algorithms/shazam-it-music-processing.... Thanks! Related: Patent infringement claim re: “Creating Shazam in Java” blogpost (2010) - https://news.ycombinator.com/item?id=9594480 https://news.ycombinator.com/item?id=9594480 - May 2015 (18 comments) Source code example of the Shazam algorithm - https://news.ycombinator.com/item?id=5724442 https://news.ycombinator.com/item?id=5724442 - May 2013 (16 comments) Creating Shazam in Java - https://news.ycombinator.com/item?id=5723863 https://news.ycombinator.com/item?id=5723863 - May 2013 (42 comments) Implementing Shazam with Java in a weekend - https://news.ycombinator.com/item?id=1702975 https://news.ycombinator.com/item?id=1702975 - Sept 2010 (22 comments) Told to remove blog posts describing patented algorithm - https://news.ycombinator.com/item?id=1496683 https://news.ycombinator.com/item?id=1496683 - July 2010 (147 comments)

rezic 4y ago

The patent infringement part 2 update was in 2010. Wonder if they ever got back to him.