Shazam은 어떻게 작동합니까? 음악 인식 알고리즘, 지문 및 처리

클럽이나 식당에서 익숙한 노래가 들립니다. 당신은 이 노래를 천 번도 넘게 들었고, 그 노래의 감성이 정말 가슴에 와 닿습니다. 내일 하트를 하고 싶은데 이름이 기억이 안나요! 다행히도 우리의 놀라운 미래 세계에서 음악 인식 소프트웨어가 설치된 전화기가 있고 저장됩니다. 소프트웨어가 노래의 이름을 알려 주기 때문에 긴장을 풀 수 있습니다. 그리고 그것이 당신의 일부가 될 때까지 계속해서 들을 수 있다는 것을 알고 있습니다. 아니면 질릴 수도 있습니다.

오디오 신호 처리의 엄청난 발전과 함께 모바일 기술은 알고리즘 개발자에게 음악 인식기를 만들 수 있는 능력을 제공했습니다. 가장 인기 있는 음악 인식 앱 중 하나는 Shazam입니다. 노래의 20초를 캡처하면 인트로, 구절 또는 후렴에 관계없이 녹음된 샘플에 대한 지문을 생성하고 데이터베이스를 참조하고 음악 인식 알고리즘을 사용하여 듣고 있는 노래를 정확히 알려줍니다. .

그러나 Shazam은 어떻게 작동합니까? Shazam의 알고리즘은 2003년 발명가 Avery Li-Chung Wang에 의해 세상에 공개되었습니다. 이 기사에서는 Shazam의 음악 인식 알고리즘의 기본 사항을 살펴보겠습니다.

아날로그에서 디지털로 - 신호 샘플링

소리란 과연 무엇일까? 우리가 만질 수는 없지만 귓가에 날아와 사물을 들리게 하는 일종의 신비로운 물질입니까?

물론 이것은 사실이 아닙니다. 우리는 실제로 소리가 공기나 물과 같은 매체를 통해 압력과 변위의 기계적 파동으로 전파되는 진동이라는 것을 알고 있습니다. 그 진동이 귀, 특히 고막에 오면 작은 뼈를 움직여 진동을 내이 깊숙이 있는 작은 유모 세포로 더 많이 전달합니다. 마지막으로, 작은 유모 세포는 청각 신경을 통해 뇌로 전달되는 전기 자극을 생성합니다.

녹음 장치는 음파의 압력을 사용하여 전기 신호로 변환하여 이 과정을 매우 유사하게 모방합니다. 공기 중의 실제 음파는 지속적인 압력 신호입니다. 마이크에서 이 신호를 만나는 첫 번째 전기 구성 요소는 이를 아날로그 전압 신호로 변환합니다. 다시 말하지만, 연속입니다. 이 연속 신호는 디지털 세계에서 그다지 유용하지 않으므로 처리되기 전에 디지털로 저장할 수 있는 이산 신호로 변환되어야 합니다. 이것은 신호의 진폭을 나타내는 디지털 값을 캡처하여 수행됩니다.

변환은 입력의 양자화를 포함하며 필연적으로 약간의 오류가 발생합니다. 따라서 아날로그-디지털 변환기는 단일 변환 대신 매우 작은 신호 조각에 대해 많은 변환을 수행합니다(샘플링이라고 하는 프로세스).

Nyquist-Shannon 정리는 연속 신호에서 특정 주파수를 캡처하는 데 필요한 샘플링 속도를 알려줍니다. 특히, 오디오 신호에서 사람이 들을 수 있는 모든 주파수를 캡처하려면 사람이 들을 수 있는 범위의 두 배 주파수에서 신호를 샘플링해야 합니다. 인간의 귀는 대략 20Hz에서 20,000Hz 사이의 주파수를 감지할 수 있습니다. 결과적으로 오디오는 44,100Hz의 샘플링 속도로 가장 자주 녹음됩니다. 이것은 컴팩트 디스크의 샘플링 속도이며 MPEG-1 오디오(VCD, SVCD, MP3)에서 가장 일반적으로 사용되는 속도이기도 합니다. (이 특정 속도는 초당 25프레임(PAL) 또는 초당 30프레임(NTSC 흑백 비디오 레코더 사용)으로 실행되는 수정된 비디오 장비에서 녹화될 수 있고 필요하다고 생각되는 20,000Hz 대역폭을 커버할 수 있기 때문에 원래 Sony에서 선택했습니다. 당시의 전문 아날로그 녹음 장비와 일치하십시오.) 따라서 녹음에 필요한 샘플의 주파수를 선택할 때 44,100Hz로 가고 싶을 것입니다.

녹음 - 사운드 캡처

샘플링된 오디오 신호를 녹음하는 것은 쉽습니다. 최신 사운드 카드에는 이미 아날로그-디지털 변환기가 함께 제공되므로 프로그래밍 언어를 선택하고 적절한 라이브러리를 찾고 샘플의 주파수, 채널 수(일반적으로 모노 또는 스테레오), 샘플 크기(예: 16비트 샘플)를 설정하면 됩니다. ). 그런 다음 다른 입력 스트림과 마찬가지로 사운드 카드에서 라인을 열고 바이트 배열에 씁니다. 다음은 Java에서 수행할 수 있는 방법입니다.

 private AudioFormat getFormat() { float sampleRate = 44100; int sampleSizeInBits = 16; int channels = 1; //mono boolean signed = true; //Indicates whether the data is signed or unsigned boolean bigEndian = true; //Indicates whether the audio data is stored in big-endian or little-endian order return new AudioFormat(sampleRate, sampleSizeInBits, channels, signed, bigEndian); } final AudioFormat format = getFormat(); //Fill AudioFormat with the settings DataLine.Info info = new DataLine.Info(TargetDataLine.class, format); final TargetDataLine line = (TargetDataLine) AudioSystem.getLine(info); line.open(format); line.start();

TargetDataLine 에서 데이터를 읽으십시오. (이 예에서 running 플래그는 다른 스레드에 의해 중지되는 전역 변수입니다. 예를 들어 STOP 버튼이 있는 GUI가 있는 경우)

 OutputStream out = new ByteArrayOutputStream(); running = true; try { while (running) { int count = line.read(buffer, 0, buffer.length); if (count > 0) { out.write(buffer, 0, count); } } out.close(); } catch (IOException e) { System.err.println("I/O problems: " + e); System.exit(-1); }

시간 영역 및 주파수 영역

이 바이트 배열에 있는 것은 시간 영역에 기록된 신호입니다. 시간 영역 신호는 시간에 따른 신호의 진폭 변화를 나타냅니다.

1800년대 초 Jean-Baptiste Joseph Fourier는 각 성분 사인파가 특정 주파수, 진폭, 그리고 단계. 원래 시간 영역 신호를 함께 형성하는 일련의 정현파를 푸리에 시리즈라고 합니다.

즉, 신호를 구성하는 각 정현파에 해당하는 주파수, 진폭 및 위상 집합을 제공함으로써 모든 시간 영역 신호를 표현할 수 있습니다. 이러한 신호 표현을 주파수 영역이라고 합니다. 어떤 면에서 주파수 영역은 시간 영역 신호에 대한 일종의 지문 또는 서명으로 작용하여 동적 신호의 정적 표현을 제공합니다.

다음 애니메이션은 1Hz 구형파의 푸리에 급수와 사인파 성분에서 (근사) 구형파를 생성하는 방법을 보여줍니다. 신호는 위의 시간 도메인과 아래의 주파수 도메인에 표시됩니다.

주파수 영역에서 신호를 분석하면 많은 것이 엄청나게 단순화됩니다. 엔지니어가 스펙트럼(주파수 영역에서 신호 표현)을 연구하고 존재하는 주파수와 누락된 주파수를 결정할 수 있기 때문에 디지털 신호 처리의 세계에서 더 편리합니다. 그런 다음 필터링을 수행하거나 일부 주파수를 늘리거나 줄이거나 주어진 주파수에서 정확한 톤을 인식할 수 있습니다.

이산 푸리에 변환

따라서 신호를 시간 영역에서 주파수 영역으로 변환하는 방법을 찾아야 합니다. 여기에서 우리는 이산 푸리에 변환(DFT)에 도움을 요청합니다. DFT는 이산(샘플링된) 신호에 대한 푸리에 분석을 수행하기 위한 수학적 방법론입니다. 동일한 간격의 함수 샘플의 유한 목록을 해당 정현파가 동일한 속도로 샘플링되었는지 고려하여 주파수에 따라 정렬된 복합 정현파의 유한 조합 계수 목록으로 변환합니다.

DFT 계산에 가장 널리 사용되는 수치 알고리즘 중 하나는 FFT(고속 푸리에 변환)입니다. FFT의 가장 일반적으로 사용되는 변형은 Cooley-Tukey 알고리즘입니다. 이것은 DFT를 여러 개의 더 작은 DFT로 재귀적으로 나누는 분할 정복 알고리즘입니다. DFT를 직접 평가하려면 O( n 2 ) 연산이 필요하지만 Cooley-Tukey FFT를 사용하면 O( n log n ) 연산에서 동일한 결과가 계산됩니다.

FFT에 적합한 라이브러리를 찾는 것은 어렵지 않습니다. 다음은 그 중 몇 가지입니다.

• C – FFTW
• C++ – 고유 FFT
• 자바 – JTransform
• 파이썬 – 넘파이
• Ruby – Ruby-FFTW3(FFTW에 대한 인터페이스)

다음은 Java로 작성된 FFT 함수의 예입니다. (FFT는 복소수를 입력으로 사용합니다. 복소수와 삼각 함수 간의 관계를 이해하려면 오일러 공식을 읽어보세요.)

 public static Complex[] fft(Complex[] x) { int N = x.length; // fft of even terms Complex[] even = new Complex[N / 2]; for (int k = 0; k < N / 2; k++) { even[k] = x[2 * k]; } Complex[] q = fft(even); // fft of odd terms Complex[] odd = even; // reuse the array for (int k = 0; k < N / 2; k++) { odd[k] = x[2 * k + 1]; } Complex[] r = fft(odd); // combine Complex[] y = new Complex[N]; for (int k = 0; k < N / 2; k++) { double kth = -2 * k * Math.PI / N; Complex wk = new Complex(Math.cos(kth), Math.sin(kth)); y[k] = q[k].plus(wk.times(r[k])); y[k + N / 2] = q[k].minus(wk.times(r[k])); } return y; }

다음은 FFT 분석 전후의 신호 예입니다.

음악 인식: 노래 지문

FFT의 한 가지 불행한 부작용은 타이밍에 대한 많은 정보를 잃는 것입니다. (이론적으로는 피할 수 있지만 성능 오버헤드는 엄청납니다.) 3분짜리 노래의 경우 모든 주파수와 크기를 볼 수 있지만 노래에서 언제 등장했는지는 알 수 없습니다. 하지만 이것이 바로 그 노래를 만드는 핵심 정보입니다! 어떻게든 우리는 각 주파수가 나타난 시점을 알아야 합니다.

이것이 우리가 일종의 슬라이딩 윈도우 또는 데이터 덩어리를 도입하고 정보의 이 부분만 변환하는 이유입니다. 각 청크의 크기는 몇 가지 다른 방법으로 결정할 수 있습니다. 예를 들어 44,100Hz에서 16비트 샘플을 사용하여 스테레오로 사운드를 녹음하면 이러한 사운드의 1초는 44,100샘플 * 2바이트 * 2채널 ≈ 176kB가 됩니다. 청크 크기로 4kB를 선택하면 노래의 1초마다 44개의 데이터 청크를 분석하게 됩니다. 오디오 식별에 필요한 세부 분석에 충분한 밀도입니다.

이제 프로그래밍으로 돌아가십시오.

 byte audio [] = out.toByteArray() int totalSize = audio.length int sampledChunkSize = totalSize/chunkSize; Complex[][] result = ComplexMatrix[sampledChunkSize][]; for(int j = 0;i < sampledChunkSize; j++) { Complex[chunkSize] complexArray; for(int i = 0; i < chunkSize; i++) { complexArray[i] = Complex(audio[(j*chunkSize)+i], 0); } result[j] = FFT.fft(complexArray); }

내부 루프에서 시간 영역 데이터(샘플)를 허수부가 0인 복소수에 넣습니다. 외부 루프에서 모든 청크를 반복하고 각각에 대해 FFT 분석을 수행합니다.

신호의 주파수 구성에 대한 정보가 있으면 노래의 디지털 지문을 형성할 수 있습니다. 이것은 전체 Shazam 오디오 인식 프로세스에서 가장 중요한 부분입니다. 여기서 주요 과제는 캡처된 주파수의 바다에서 가장 중요한 주파수를 구별하는 방법입니다. 직관적으로 가장 높은 크기(일반적으로 피크라고 함)의 주파수를 검색합니다.

그러나 한 곡에서 강한 주파수 범위는 낮은 C - C1(32.70Hz)과 높은 C - C8(4,186.01Hz) 사이에서 다양할 수 있습니다. 이것은 커버할 엄청난 간격입니다. 따라서 전체 주파수 범위를 한 번에 분석하는 대신 중요한 음악 구성 요소의 공통 주파수를 기반으로 선택한 몇 개의 더 작은 간격을 선택하고 각각을 개별적으로 분석할 수 있습니다. 예를 들어 이 사람이 Shazam 알고리즘을 구현하기 위해 선택한 간격을 사용할 수 있습니다. 저음(예: 베이스 기타 포함)의 경우 30Hz - 40Hz, 40Hz - 80Hz 및 80Hz - 120Hz이고 중음 및 고음의 경우 120Hz - 180Hz 및 180Hz - 300Hz입니다. (보컬과 대부분의 다른 악기를 다룹니다).

이제 각 간격 내에서 크기가 가장 높은 주파수를 간단히 식별할 수 있습니다. 이 정보는 노래의 이 청크에 대한 서명을 형성하고 이 서명은 노래 전체의 지문의 일부가 됩니다.

 public final int[] RANGE = new int[] { 40, 80, 120, 180, 300 }; // find out in which range is frequency public int getIndex(int freq) { int i = 0; while (RANGE[i] < freq) i++; return i; } // result is complex matrix obtained in previous step for (int t = 0; t < result.length; t++) { for (int freq = 40; freq < 300 ; freq++) { // Get the magnitude: double mag = Math.log(results[t][freq].abs() + 1); // Find out which range we are in: int index = getIndex(freq); // Save the highest magnitude and corresponding frequency: if (mag > highscores[t][index]) { points[t][index] = freq; } } // form hash tag long h = hash(points[t][0], points[t][1], points[t][2], points[t][3]); } private static final int FUZ_FACTOR = 2; private long hash(long p1, long p2, long p3, long p4) { return (p4 - (p4 % FUZ_FACTOR)) * 100000000 + (p3 - (p3 % FUZ_FACTOR)) * 100000 + (p2 - (p2 % FUZ_FACTOR)) * 100 + (p1 - (p1 % FUZ_FACTOR)); }

녹음이 완벽한 조건(즉, "농아실")에서 수행되지 않는다고 가정해야 하며 결과적으로 퍼즈 요소를 포함해야 합니다. Fuzz factor 분석은 심각하게 받아들여야 하며 실제 시스템에서 프로그램은 녹음 조건에 따라 이 매개변수를 설정할 수 있는 옵션이 있어야 합니다.

오디오 검색을 쉽게 하기 위해 이 서명은 해시 테이블의 키가 됩니다. 해당 값은 노래 ID(노래 제목 및 아티스트)와 함께 이 주파수 세트가 노래에 나타난 시간입니다. 다음은 이러한 레코드가 데이터베이스에 표시되는 방식의 예입니다.

이 음악 식별 프로세스를 통해 전체 노래 라이브러리를 실행하면 라이브러리에 있는 모든 노래의 완전한 지문으로 데이터베이스를 구축할 수 있습니다.

음악 알고리즘: 노래 식별

현재 동아리에서 재생되고 있는 곡을 식별하기 위해 휴대폰으로 해당 곡을 녹음하고, 위와 동일한 오디오 핑거프린팅 과정을 거쳐 녹음을 진행합니다. 그런 다음 일치하는 해시 태그에 대한 데이터베이스 검색을 시작할 수 있습니다.

그렇게 되면 많은 해시 태그가 여러 노래의 음악 식별자에 해당합니다. 예를 들어, 노래 A의 일부가 노래 E의 일부와 똑같이 들릴 수 있습니다. 물론 이것은 놀라운 일이 아닙니다. 음악가는 항상 서로의 릭과 리프를 "빌려왔습니다". 요즘 프로듀서는 다른 노래를 모두 샘플링합니다. 시간. 해시 태그를 일치시킬 때마다 가능한 일치 항목의 수는 줄어들지만 이 정보만으로는 일치 항목을 단일 노래로 좁힐 수 없습니다. 따라서 음악 인식 알고리즘으로 확인해야 할 사항이 한 가지 더 있습니다. 바로 타이밍입니다.

클럽에서 녹음한 샘플은 노래의 어느 지점에서나 올 수 있으므로 일치하는 해시의 타임스탬프를 샘플의 타임스탬프와 단순히 일치시킬 수 없습니다. 그러나 여러 개의 일치하는 해시를 사용하면 일치의 상대적 타이밍을 분석할 수 있으므로 확실성을 높일 수 있습니다.

예를 들어 위의 표를 보면 해시 태그 30 51 99 121 195 가 Song A와 Song E 모두에 해당하는 것을 볼 수 있습니다. 1초 후에 해시 34 57 95 111 200 과 일치하면 하나 더 있습니다. 노래 A와 일치하지만 이 경우 해시와 시간 차이가 모두 일치한다는 것을 알고 있습니다.

 // Class that represents specific moment in a song private class DataPoint { private int time; private int songId; public DataPoint(int songId, int time) { this.songId = songId; this.time = time; } public int getTime() { return time; } public int getSongId() { return songId; } }

녹음된 노래의 순간으로 i 1 과 i 2 를, 데이터베이스에서 노래의 순간으로 j 1 과 j 2 를 취합시다. 다음과 같은 경우 시차 일치가 있는 두 개의 일치 항목이 있다고 말할 수 있습니다.

<span style=font-family: TimesNewRoman;> RecordedHash(i 1 ) = SongInDBHash(j 1 ) AND RecordedHash(i 2 ) = SongInDBHash(j 2 ) </span>

<span style=font-family: TimesNewRoman;>그리고</span>

<span style=font-family: TimesNewRoman;> abs(i 1 - i 2 ) = abs(j 1 - j 2 ) </span>

이것은 처음, 중간 또는 끝에서 노래를 녹음할 수 있는 유연성을 제공합니다.

마지막으로, 우리가 클럽에서 녹음하는 노래의 모든 순간이 스튜디오에서 녹음된 우리 라이브러리의 동일한 노래의 모든 해당 순간과 일치하지 않을 것입니다. 녹음에는 경기에서 약간의 오류가 발생할 수 있는 많은 노이즈가 포함됩니다. 따라서 일치 목록에서 올바른 노래를 제외한 모든 노래를 제거하는 대신 맨 마지막에 일치하는 모든 노래를 가능성의 내림차순으로 정렬하고 가장 좋아하는 노래는 순위 목록의 첫 번째 노래입니다.

위에서 아래로

"Shazam은 어떻게 작동합니까?"라는 질문에 답하기 위해 다음은 위에서 아래로 전체 음악 인식 및 일치 프로세스에 대한 개요입니다.

이러한 종류의 시스템에서는 데이터베이스가 상당히 커질 수 있으므로 일종의 확장 가능한 데이터베이스를 사용하는 것이 중요합니다. 특별한 관계가 필요하지 않고 데이터 모델이 상당히 단순해지기 때문에 일종의 NoSQL 데이터베이스를 사용하는 것이 좋습니다.

Shazam은 어떻게 작동합니까? 이제 당신은 알고

이러한 종류의 노래 인식 소프트웨어는 노래 간의 유사점을 찾는 데 사용할 수 있습니다. 이제 Shazam이 작동하는 방식을 이해했으므로 택시 라디오에서 재생되는 향수를 불러일으키는 노래를 단순히 Shazam하는 것 이상의 응용 프로그램을 사용할 수 있음을 알 수 있습니다. 예를 들어, 음악의 표절을 식별하거나 블루스, 재즈, 록, 팝 또는 기타 장르의 일부 개척자에게 초기 영감을 준 사람을 찾는 데 도움이 될 수 있습니다. 아마도 좋은 실험은 노래 샘플 데이터베이스를 바흐, 베토벤, 비발디, 바그너, 쇼팽, 모차르트의 클래식 음악으로 채우고 노래 간의 유사점을 찾는 것입니다. 밥 딜런(Bob Dylan), 엘비스 프레슬리(Elvis Presley), 로버트 존슨(Robert Johnson)도 표절이라고 생각할 것입니다!

그러나 여전히 우리는 그들을 비난할 수 없습니다. 왜냐하면 음악은 우리가 듣고 기억하고 머리 속에서 반복하는 파도일 뿐이기 때문에 스튜디오에서 녹음하고 다음 위대한 음악 천재에게 전달할 때까지 진화하고 변화합니다.