3 ms·

Application of Locality Sensitive Hashing to audio fingerprinting

31 points by pncnmnp 3y ago

abetusk 3y ago
Does anyone have experience with how well this works?
- johanvts 3y ago
  How well it works for identifying music is going to be an issue of how well you can construct the feature vector which is not covered. If you map every song in to the same small subset of space, LSH will struggle. Map them to well separated places and it will shine.
  - bravura 3y ago
    This is wrong, or misleading at best. It's a known difficult open problem to create a good audio representation (feature vector). Good, in the case of LSH, would be that representation distance correlates well with human perception. For something like Shazam, you want this representation to be invariant to minor transformations of the audio. That's the interesting problem.
    - johanvts 3y ago
      How is that not aligned with what I’m saying? You add some detail, but that doesn’t make me wrong.
- pncnmnp 3y ago
  Check out Steve and Iran's website https://musicinformationretrieval.com/ https://musicinformationretrieval.com/ They have a bunch of Colab notebooks where they explore various music IR ideas, including LSH. GitHub: https://github.com/iranroman/musicinformationretrieval.com/ https://github.com/iranroman/musicinformationretrieval.com/
bequanna 3y ago
Does anyone know how this approach differs from the approach taken by the popular(ish) dejavu project? https://github.com/worldveil/dejavu https://github.com/worldveil/dejavu
- willseth 3y ago
  Last I checked Dejavu doesn't use LSH or any approximations. It simply queries for exact matches, "aligns" them, and determines if there is enough signal from the noise to consider it a match.
  - bequanna 3y ago
    Ahh, I see. The approach here is just getting vector nearest neighbors. I guess I don’t see how this could work like “Shazam” when you’re comparing the vector of some sample to the vector for the whole song.
    - willseth 3y ago
      Oh, no, it's not for the whole song. For each song, you take N samples, each sample gets converted into a fingerprint, and all of the fingerprints are stored in a database. Then when you query, you perform the same sample-to-fingerprint computation, and query the database for matching fingerprints. The database will return many false positives, but only 1 will "align", meaning the relative timing of the fingerprints returned is in sync with an actual song in the database. Once the number of aligned fingerprints reaches a set threshold, you can stop and return it as a result. That's how it performs subset matching.
      - bequanna 3y ago
        Gotcha. So taking n overlapping samples for the song, fingerprinting then vectorizing each. Then doing the same thing for the captured sample and getting nearest neighbors. I’ve used dejavu for a personal project and it is quite fast. Is the LSH approach somehow more efficient/attractive now because we’ve made strides in vector nearest neighbors search?

31 points by pncnmnp 3y ago

abetusk 3y ago

Does anyone have experience with how well this works?

johanvts 3y ago
How well it works for identifying music is going to be an issue of how well you can construct the feature vector which is not covered. If you map every song in to the same small subset of space, LSH will struggle. Map them to well separated places and it will shine.
- bravura 3y ago
  This is wrong, or misleading at best. It's a known difficult open problem to create a good audio representation (feature vector). Good, in the case of LSH, would be that representation distance correlates well with human perception. For something like Shazam, you want this representation to be invariant to minor transformations of the audio. That's the interesting problem.
  - johanvts 3y ago
    How is that not aligned with what I’m saying? You add some detail, but that doesn’t make me wrong.
pncnmnp 3y ago
Check out Steve and Iran's website https://musicinformationretrieval.com/ https://musicinformationretrieval.com/ They have a bunch of Colab notebooks where they explore various music IR ideas, including LSH. GitHub: https://github.com/iranroman/musicinformationretrieval.com/ https://github.com/iranroman/musicinformationretrieval.com/

bequanna 3y ago

Does anyone know how this approach differs from the approach taken by the popular(ish) dejavu project? https://github.com/worldveil/dejavu https://github.com/worldveil/dejavu

willseth 3y ago
Last I checked Dejavu doesn't use LSH or any approximations. It simply queries for exact matches, "aligns" them, and determines if there is enough signal from the noise to consider it a match.
- bequanna 3y ago
  Ahh, I see. The approach here is just getting vector nearest neighbors. I guess I don’t see how this could work like “Shazam” when you’re comparing the vector of some sample to the vector for the whole song.
  - willseth 3y ago
    Oh, no, it's not for the whole song. For each song, you take N samples, each sample gets converted into a fingerprint, and all of the fingerprints are stored in a database. Then when you query, you perform the same sample-to-fingerprint computation, and query the database for matching fingerprints. The database will return many false positives, but only 1 will "align", meaning the relative timing of the fingerprints returned is in sync with an actual song in the database. Once the number of aligned fingerprints reaches a set threshold, you can stop and return it as a result. That's how it performs subset matching.
    - bequanna 3y ago
      Gotcha. So taking n overlapping samples for the song, fingerprinting then vectorizing each. Then doing the same thing for the captured sample and getting nearest neighbors. I’ve used dejavu for a personal project and it is quite fast. Is the LSH approach somehow more efficient/attractive now because we’ve made strides in vector nearest neighbors search?