샤잠 작동 원리 (2022)

 (cameronmacleod.com)
2P by GN⁺ | ★ favorite | 댓글 1개
  • Shazam은 몇 초짜리 마이크 녹음만으로 곡을 찾기 위해, 오디오 전체를 비교하지 않고 오디오 지문(fingerprint) 을 만들어 데이터베이스에서 검색함
  • 파형을 그대로 밀어가며 비교하는 방식은 1,000만 곡 규모와 마이크 노이즈, 음량 변화, 주파수 효과 때문에 현실적으로 맞지 않음
  • 핵심 흐름은 오디오를 spectrogram으로 바꾸고 강한 주파수 peak를 찾은 뒤, peak 쌍을 hash로 저장해 빠르게 비교하는 방식임
  • peak는 노이즈에도 상대적으로 잘 남고 저장량을 줄여주지만, 시간과 주파수에 고르게 분포해야 곡의 어느 구간에서도 인식 가능함
  • 인식 단계는 일치한 hash의 Track time - Sample time 차이를 histogram으로 묶고, 한 bin에 가장 크게 몰리는 곡을 정답으로 고름

Shazam이 풀어야 하는 문제

  • Shazam은 주변에서 재생 중인 곡을 몇 초간 녹음한 뒤 데이터베이스에서 찾아 결과를 보여주는 앱임
  • 앱이 되기 전 Shazam은 전화번호 기반 서비스였음
    • 사용자는 번호로 전화를 걸고 휴대전화 마이크를 음악 쪽에 대야 했음
    • 30초 뒤 Shazam이 전화를 끊고 듣고 있던 곡 정보를 문자로 보냈음
    • 2002년 당시 휴대전화 통화 품질은 곡 인식을 더 어렵게 만들었음
  • 작은 예제라면 오디오 조각을 전체 트랙 위에서 조금씩 이동시키며 일치 여부를 확인할 수 있음
    • 하지만 어떤 곡인지 모르는 상태에서 1,000만 곡 데이터베이스를 검색하면 시간이 크게 늘어남
  • 실제 마이크 샘플은 배경 소음, 주파수 효과, 음량 변화로 파형 모양이 달라질 수 있어 단순 sliding 비교가 잘 맞지 않음

전체 시스템 흐름

  • Shazam 방식은 register와 recognise 흐름으로 나뉨
    • register는 나중에 찾을 수 있도록 곡을 저장하는 흐름임
    • recognise는 짧은 오디오 구간이 어떤 곡인지 찾는 흐름임
  • 두 흐름은 같은 전처리 단계를 거침
    • 오디오의 spectrogram 계산
    • spectrogram에서 가장 강한 주파수 성분인 peak 찾기
    • peak들을 쌍으로 묶어 hash 생성
  • register 흐름은 계산한 hash를 데이터베이스에 저장함
  • recognise 흐름은 새 오디오에서 만든 hash를 데이터베이스의 hash와 비교해 matching 단계에서 곡을 식별함

Spectrogram 계산

  • Fourier transform은 오디오에 어떤 주파수가 들어 있는지 알려줌
    • 20Hz sine wave에 Fourier transform을 적용하면 20Hz 근처에 큰 spike가 나타남
    • sine wave는 단일 주파수만 포함하기 때문에 pure tone이라고도 불림
  • Fourier transform 결과는 frequency spectrum임
    • 시간축 중심의 표현은 time domain임
    • 주파수축 중심의 표현은 frequency domain임
    • frequency spectrum의 Y축은 각 주파수 성분의 강도를 나타내며, 강한 성분일수록 time-domain 신호에서 더 잘 들림
  • 여러 sine wave를 더하면 각 wave의 주파수 성분이 결합됨
    • 20Hz sine wave에 절반 세기의 50Hz sine wave를 더하면 20Hz spike와 더 작은 50Hz spike가 나타남
    • 모든 오디오 신호는 이런 wave들로 재구성될 수 있음
  • frequency domain은 time domain에서 잘 보이지 않는 정보를 드러냄
    • 노이즈가 추가되어 time-domain 모양이 달라져도 frequency domain에서는 주요 주파수 spike가 여전히 뚜렷할 수 있음
  • 곡 전체에 한 번만 Fourier transform을 적용하면 전체 주파수 강도만 보이지만, 실제 곡의 주파수는 시간에 따라 변함
    • 곡을 작은 구간으로 나누고 각 구간에 Fourier transform을 적용한 뒤 합치면 spectrogram이 됨
    • spectrogram은 시간, 주파수, 강도를 함께 표현하며 강도는 색으로 표시될 수 있음
  • 예시인 “Like a Stone”의 spectrogram에서는 가장 밝은 지점, 즉 강한 주파수 대부분이 5000Hz 아래에 나타남
    • 음악에서 이런 분포는 흔하며, 대부분의 피아노 주파수 범위는 27Hz-4186Hz임

Peak 기반 fingerprint

  • 오디오 fingerprint는 spectrogram에서 peak를 찾는 데서 시작함
    • peak는 특정 시점에서 가장 큰 주파수 성분임
    • 음악에서는 기타 솔로의 강한 음처럼 해당 시점에서 가장 큰 음이 peak가 될 수 있음
  • peak는 노이즈의 영향을 상대적으로 덜 받음
    • peak를 알아볼 수 없게 만들려면 노이즈가 해당 peak보다 더 커야 함
    • spectrogram peak는 트랙에서 가장 강한 주파수 성분임
  • peak만 저장하면 fingerprint에 필요한 데이터량이 줄어듦
    • 모든 주파수 정보를 저장하지 않고 가장 큰 주파수 성분만 남김
    • 검색할 데이터가 줄어 fingerprint 검색이 빨라짐
  • peak는 시간과 주파수 양쪽에서 고르게 분포해야 함
    • 시간상 한쪽에만 몰리면 곡의 나머지 구간 샘플을 인식할 수 없음
    • 주파수 대역이 좁게 몰리면 자동차 경적 같은 특정 대역의 큰 소음이 peak 선택을 바꿔 해당 구간을 알아보기 어려워짐

Maximum filter로 peak 찾기

  • peak를 고르게 찾기 위해 이미지 처리의 maximum filter 기법을 사용할 수 있음
  • maximum filter는 각 pixel 주변 이웃 영역에서 최대값을 찾고, 해당 pixel을 그 local maximum 값으로 바꿈
    • 예시는 각 pixel 주변의 3x3 영역을 살피는 방식임
    • 이 처리는 local peak를 주변 영역으로 확장하는 효과가 있음
  • maximum-filtered spectrogram은 원래 spectrogram의 저해상도 버전처럼 보임
    • 신호의 peak가 확장되어 다른 pixel을 차지하기 때문임
    • 같은 색의 box는 원본 이미지의 local peak 하나에 대응함
  • maximum filter에는 local maximum을 찾을 box 크기 파라미터가 있음
    • 작은 box를 쓰면 더 많은 peak가 나옴
    • 큰 box를 쓰면 더 적은 peak가 나옴
  • peak 위치는 원래 spectrogram과 filtering된 spectrogram의 값이 같은 지점을 찾아 복원함
    • peak가 아닌 지점은 local peak 값으로 바뀌어 값이 달라짐
    • 값이 그대로 남은 지점만 peak임
  • 모든 peak를 모아 그리면 constellation map이 됨
    • 밤하늘 이미지처럼 보이기 때문에 이런 이름이 붙음
  • peak 수는 fingerprint 크기에 직접 영향을 줌
    • 수백만 곡을 저장해야 한다면 fingerprint를 작게 유지하는 것이 중요함
    • peak를 줄이면 정확도도 낮아지고, sample을 올바른 곡과 matching할 기회가 감소함
  • peak를 줄이는 방식은 두 가지임
    • 상위 N개 peak를 사용하며, N은 짧은 곡이 과대표집되지 않도록 오디오 길이에 비례해야 함
    • 특정 threshold보다 큰 peak를 모두 사용하며, 시간당 fingerprint 크기를 보장하지는 않지만 더 정확할 수 있음

Peak 쌍을 hash로 만들기

  • fingerprint가 단일 spectrogram peak들의 모음이라면 중복이 빠르게 늘어남
    • 각 peak의 주파수를 10bit로 표현하면 2^10=1024개의 개별 주파수를 표현할 수 있음
    • 트랙당 수천 개 지점이 있으면 반복이 많아짐
  • fingerprint는 고유성이 중요함
    • 고유성이 높을수록 검색이 빨라짐
    • 더 많은 곡을 인식하는 데 도움이 됨
  • Shazam 방식은 단일 peak가 아니라 peak 쌍으로 hash를 만듦
    • hash에는 두 peak의 주파수 fA, fB와 두 peak 사이의 시간 차이 ΔT가 들어감
    • 각 peak가 10bit 주파수 정보를 갖고 ΔT도 10bit로 표현된다면 총 30bit 정보가 됨
    • 2^30=1,073,741,824가지 가능성은 단일 point의 1024가지보다 훨씬 큼
  • pair 생성에는 anchor point와 target zone을 사용함
    • point 하나를 anchor point로 선택함
    • anchor point에 대한 spectrogram target zone을 계산함
    • target zone 안의 모든 point와 anchor point를 pair로 만듦
  • Shazam 논문은 target zone 선택 방식을 자세히 설명하지 않음
    • 논문 이미지에서는 target zone이 anchor point보다 약간 뒤 시간에서 시작하고, anchor point의 주파수를 중심으로 놓인 형태임
  • 생성된 pair는 데이터베이스에 hash로 저장됨
    • hash 구성 요소는 fA, fB, ΔT임
    • 추가 정보로 Point A time과 Track ID를 저장함
    • Point A time과 Track ID는 나중에 matching에서 특정 곡의 특정 시점을 찾는 데 쓰임
  • 특정 트랙의 모든 hash 모음이 해당 트랙의 fingerprint가 됨

Matching 방식

  • recognise 흐름은 sample에서 fingerprint를 만들고, 이를 이미 데이터베이스에 저장된 fingerprint와 비교함
  • matching 알고리듬은 네 단계로 진행됨
    • sample fingerprint와 일치하는 모든 hash를 데이터베이스에서 가져옴
    • hash를 곡별로 group화함
    • 각 곡에 대해 hash들이 시간상 정렬되는지 확인함
    • 정렬된 hash가 가장 많은 트랙을 선택함
  • abracadabra는 3-tuple인 _(fA, fB, ΔT)_를 그대로 검색하지 않고 hash(fA, fB, ΔT)가 반환하는 단일 값으로 저장함
    • hash마다 세 값을 검색하는 대신 하나의 값을 검색할 수 있음
  • 데이터베이스의 각 hash에는 Track ID가 연결되어 있어 곡별 grouping이 가능함
    • 이렇게 grouping한 뒤 각 후보 트랙에 점수를 매길 수 있음
  • sample이 어떤 곡과 일치한다면 sample 안의 hash들은 원곡의 한 구간에 잘 정렬되어야 함
    • 노이즈는 sample에 다른 시점의 peak처럼 보이는 peak를 만들 수 있음
    • hash가 잘못된 곡과 일치하는 경우도 있음
  • 정렬 여부는 각 matching hash에 대해 Track time - Sample time 값을 계산해 확인함
    • 진짜 matching hash들은 같은 차이값을 공유함
    • 예시에서는 차이값 10을 가진 행들이 true match이고, 다른 차이값은 false match임
  • 차이값들을 histogram으로 만들고 가장 큰 bin을 곡의 score로 사용함
    • 좋은 match가 아닌 곡은 모든 bin 값이 낮음
    • 좋은 match인 곡은 한 bin에서 큰 spike가 생김
  • 단순히 matching hash 수가 가장 많은 곡을 고르지 않는 이유는 곡 길이 편향 때문임
    • 긴 곡은 짧은 곡보다 match 수가 많아질 가능성이 큼
    • Spotify에는 4시간이 넘는 트랙도 있어 결과가 크게 치우칠 수 있음

abracadabra와 참고 자료

함께 보면 좋은 글 β

GN⁺   [-]
Hacker News 의견들

  • Wall Street Journal이 Shazam을 설명한 잘 만든 영상이 있음
    https://www.wsj.com/video/series/in-depth-features/how-shaza...
    Chris, Shazam 공동창업자

    • Shazam이 San Diego의 Rancho Bernardo에 사무실을 둔 이유가, 영국으로 가기 전 원래 San Diego 출신이었기 때문인지 궁금함
      Lawn Love가 2014~2018년에 그 위층 스위트를 빌렸는데, 그 사무실의 Shazam 모바일 앱 개발자들은 인수 이후에도 조용히 지냈고 축하 샴페인 소리도 들은 적이 없음

  • Shazam이 2008년에 나왔을 때는 해시 기반 접근이 영리한 선택이었음
    나라면 모든 곡을 가능한 한 계산 효율적으로 해시로 바꾸는 방법부터 만들었을 것임
    오늘 출시했다면 기본 연구개발 방향이 모델 학습이었을 텐데, 훨씬 덜 효율적이고 호스팅 비용도 더 비쌌을 수 있음
    모델이 잘할 것처럼 느껴지는 문제이긴 하지만, 곡 수가 유한하다는 점에서는 해시 방식이 훨씬 성능이 좋을 가능성이 큼

    • 정확히는 각 곡을 하나의 해시로 바꾸는 게 아니라, 각 곡을 수백~수천 개의 해시로 바꾸는 방식임
      짧은 샘플에서 나온 수십 개, 많아야 낮은 수백 개 정도의 해시가 얼마나 많이, 대체로 연속적으로 맞는지 찾는 구조임
      오늘날에도 모델 학습으로 하지는 않을 것 같음. 매일 엄청나게 많은 새 곡이 추가되므로 계속 재학습해야 하기 때문임
      해시는 효율뿐 아니라 전반적인 견고성 면에서도 여전히 더 나은 접근으로 보임
    • 1975년의 영리한 접근은 Parsons code였고, 이것도 머릿속으로 계산 가능한 노래 해시화에 가까웠음
      그런 다음 사전에서 단어를 찾듯 곡을 찾을 수 있었고, 이 아이디어가 쉽게 사라지지 않았으면 함
      [1]: https://en.wikipedia.org/wiki/Parsons_code
    • 사소한 정정이지만 Shazam은 2008년이 아니라 2002년 전화 연결 서비스로 출시됐고, 결과를 문자메시지로 보내줬음
      첫 휴대폰 앱은 2006년 BREW용이었음
      2008년은 Apple이 App Store를 출시한 시점일 뿐이고, 그 전에는 제3자가 iPhone 앱을 만들 수 없었음
    • 솔직히 Shazam 같은 도구에서는 데이터베이스+해싱 알고리즘과 자기지도 모델 사이에 근본적 차이가 크지 않음
      둘 다 훌륭한 색인화와 압축 해법이고, 다만 데이터 규모가 다를 뿐임
    • 이걸 모델로 학습한다면 새 곡을 추가할 때마다 전체 학습 과정을 다시 돌리지 않도록 어떻게 피할 수 있을지 궁금함
      새 곡마다 완전 재학습 없이 임베딩 벡터를 계산할 수 있는 임베딩 모델을 만들 방법이 있을지도 모르겠음

  • Shazam은 20년 동안 마법 같은 느낌이 사라지지 않은 드문 제품임
    기술자들이 지향해야 할 대상에 정말 가까움

    • 기술적으로 아는 사람에게 음악 지문 추출은 이해 가능한 구체적 문제지만, 이미 해결된 방식을 보지 않고 세부로 들어가면 꽤 어려운 문제임
      동물이나 사물 이미지 인식처럼 겉보기엔 비슷하지만 대부분 이상한 기계학습 마법에 가까운 기능과 달리, 흔치 않지만 이해 가능한 문제 영역에 들어맞음
    • 동시에 “탭하면 듣고 바로 결과”였던 앱이 느리고 광고가 잔뜩 붙은 비대한 앱으로 변했음
      이전 세대 iPhone에서 제때 로드도 못 해서 결국 앱을 지웠던 기억이 있음
    • Google은 한 단계 더 끌어올렸음
      Now Playing 기능은 계속 노래를 감지해 기록에 남기고, Google Assistant에서는 흥얼거리는 것만으로도 곡을 검색할 수 있음
      안정적으로 동작하진 않지만 가끔은 정확히 맞힘
    • 오히려 더 마법처럼 변했음
      America’s Got Talent에서 누군가 부르던 노래를 찾으려 했더니, 결과가 AGT에 나온 그 가수로 돌아와서 놀랐음
      TV 프로그램까지 색인하는 건가 싶었음
    • 기술자들은 그런 제품을 지향함
      하지만 제품 관리자는 보너스와 휴가를 받으려고 제품을 계속 망가뜨리지 않으면 뭘 하겠나 싶음

  • Chromaprint도 있고, 약간 다른 방식으로 동작함
    스펙트럼의 최댓값이 아니라 음높이 변화 패턴을 기반으로 함
    Chromaprint는 오디오 지문과 MusicBrainz 녹음을 연결하는 대형 공개 데이터베이스 AcoustID에서 쓰임
    Shazam만큼 상업적 지원이 많지 않은데도 그 안에 음악이 엄청나게 많다는 점이 놀라움
    [1]: https://oxygene.sk/2011/01/how-does-chromaprint-work/

    • Chromaprint는 곡 전체를 비교해야 하지 않나 싶음
      중복 탐지에는 좋지만, Shazam의 지문 설계는 짧은 조각을 전체 곡에 매칭할 수 있게 해줌

  • 스펙트로그램이 무엇을 하는지 잘 포착한 훌륭한 글이고, 오디오 지문 추출이 어떻게 동작하는지 이해하고 싶은 사람에게 필독에 가까움
    다른 매체에도 비슷한 근사 알고리즘이 있으니, 현실 세계의 해싱을 이해하려면 이 글을 차분히 공부해볼 만함

    • 일반적인 스펙트로그램 기법은 Shazam 이전에 Phillips가 이미 발명했음
      Shazam이 한 일은 거짓 양성을 줄이기 위해 조합적으로 해시화한 것임

  • 노래가 아니라 장르 분류와 새 곡 시그니처가 만들어내는 하위 장르 분기를 알고리즘 매칭으로 다루는 훌륭한 사이트가 있음
    개인 사이드 프로젝트로 운영되는 놀라운 자료인데, 호스팅 문제 같은 이유로 사라질 위험이 있어 보임
    예전에 Pandora의 Music DNA나 LastFM의 비슷한 기능이 있었지만, 이 사이트는 2023년까지 인류가 만든 음악 전체의 시각적 연결망 같아서 사라지면 웹 전체의 손실일 것임
    Every Noise At Once
    https://everynoise.com

  • 이 방식이 얼마나 직관적인지, 그리고 우리 자신의 인식 과정과 얼마나 잘 맞는지가 놀라움
    대략 멜로디 조각을 식별한 다음, 그것들을 순서대로 맞춰보는 방식임
    우리가 5개, 7개, 10개 음만 듣고도 뭔가를 알아차리는 것과 비슷함
    음량 피크 같은 것에 의존하는 다른 노래 지문 추출 방식도 읽어본 것 같은데, 그런 방식도 똑같이 잘 동작할 수는 있어도 우리 뇌가 하는 방식과는 전혀 맞지 않음
    이 방식은 “인공적 부산물”에 기대는 게 아니라 기본적으로 우리가 하는 방식과 비슷하게 작동해서 꽤 멋짐
    기술적으로는 항상 멜로디는 아니지만, 대부분은 멜로디일 가능성이 큼

  • Shazam이 시간축이 선형이 아니거나 일정하지 않은 경우를 어떻게 처리하는지 궁금함
    테이프, 와우 앤 플러터, 계속 빨라졌다 느려지는 상황 같은 경우임
    아는 한 지문 추출은 시간에 매우 민감하고, 50ms 정도 조각으로 잘라도 완전히 해결되지는 않음
    마지막으로 봤을 때 이런 문제의 일반 기법인 동적 시간 워핑(Dynamic Time Warping)은 계산 비용이 너무 컸음

  • 관련 글들임. 더 있으면 궁금함
    How Shazam Works (2003 Paper) - https://news.ycombinator.com/item?id=33299853 - 2022년 10월, 댓글 1개
    Creating Shazam in Java (2010) - https://news.ycombinator.com/item?id=32530056 - 2022년 8월, 댓글 36개
    Shazam turns 20 - https://news.ycombinator.com/item?id=32520593 - 2022년 8월, 댓글 227개
    How Shazam Works (2015) - https://news.ycombinator.com/item?id=23806142 - 2020년 7월, 댓글 7개
    Designing an audio adblocker - https://news.ycombinator.com/item?id=18855029 - 2019년 1월, 댓글 186개
    Show HN: A radio/podcast adblocker featuring ML and Shazam-like fingerprinting - https://news.ycombinator.com/item?id=18459058 - 2018년 11월, 댓글 2개
    Show HN: Shazam-like acoustic fingerprinting of continuous audio streams - https://news.ycombinator.com/item?id=15809291 - 2017년 11월, 댓글 76개
    How Shazam Works (2015) - https://news.ycombinator.com/item?id=15350729 - 2017년 9월, 댓글 13개
    Tell HN: Shazam picks up song from my kitchen light - https://news.ycombinator.com/item?id=11593305 - 2016년 4월, 댓글 2개
    How Shazam works - https://news.ycombinator.com/item?id=9870408 - 2015년 7월, 댓글 48개
    Patent infringement claim re: “Creating Shazam in Java” blogpost (2010) - https://news.ycombinator.com/item?id=9594480 - 2015년 5월, 댓글 18개
    The Shazam Effect (2014) - https://news.ycombinator.com/item?id=9593429 - 2015년 5월, 댓글 37개
    The Shazam Effect - https://news.ycombinator.com/item?id=8634357 - 2014년 11월, 댓글 34개
    Ask HN: Is there an audio search technology that finds exact and similar audio? - https://news.ycombinator.com/item?id=8420141 - 2014년 10월, 댓글 3개
    Source code example of the Shazam algorithm - https://news.ycombinator.com/item?id=5724422 - 2013년 5월, 댓글 16개
    Creating Shazam in Java - https://news.ycombinator.com/item?id=5723863 - 2013년 5월, 댓글 43개
    An Industrial-Strength Audio Search Algorithm (Shazam) - https://news.ycombinator.com/item?id=2621103 - 2011년 6월, 댓글 4개
    Shazam's Search for Songs Creates New Music Jobs - https://news.ycombinator.com/item?id=2215295 - 2011년 2월, 댓글 1개
    How does the music-identifying app Shazam work its magic? - https://news.ycombinator.com/item?id=2214992 - 2011년 2월, 댓글 2개
    Implementing Shazam with Java in a weekend - https://news.ycombinator.com/item?id=1702975 - 2010년 9월, 댓글 23개
    Shazam: not magic after all - https://news.ycombinator.com/item?id=909263 - 2009년 10월, 댓글 28개
    How does the music-identifying app Shazam work its magic? - https://news.ycombinator.com/item?id=893353 - 2009년 10월, 댓글 16개

  • 팝 음악 산업이 장르 기반 히트곡을 만들려고 하는 비슷한 공학의 반대 방향 접근처럼 보임

답변달기