Baru-baru ini, BI.ZONE berpartisipasi dalam konferensi HighLoad ++. Jelas bahwa kami tiba di sana bukan hanya untuk menatap stan orang lain, tetapi membawa sesuatu yang menarik. Karyawan dari berbagai departemen perusahaan menyiapkan tugas untuk tamu konferensi, untuk solusi yang kami tawarkan hadiah. Salah satu tugas Golang didedikasikan untuk pengenalan suara. Kami meminta pengarangnya untuk menceritakan tentang dia.
Pernyataan masalah
Dalam tugas kami, kami perlu mengindeks sejumlah trek dan mempelajari cara mencari di database komposisi asli dengan sampelnya. Dalam hal ini, sampel mungkin berisik, direkam pada mikrofon yang buruk, mungkin memiliki frekuensi yang berbeda. Sebagian besar kode telah ditulis untuk peserta, ia hanya perlu menerapkan fungsi sidik jari, yang menghilangkan sidik jari dari trek.
Cara merekam suara
Jelas bahwa trek apa pun adalah gelombang mekanis yang memiliki sifat analog. Gelombang dalam fisika memiliki dua karakteristik: frekuensi dan amplitudo. Berkenaan dengan gelombang suara, untuk kesederhanaan, kita dapat mengasumsikan bahwa amplitudo adalah volume dan frekuensi adalah nada, meskipun pada kenyataannya suara tinggi tampaknya lebih keras bagi seseorang pada amplitudo yang sama.
Yaitu, dari sudut pandang fisika, masing-masing komposisi dijelaskan oleh fungsi kontinu, yang berarti bahwa setiap bagian kecil dari lagu tersebut akan mengandung jumlah informasi yang tak terbatas (walaupun jika ini adalah semacam post-punk, maka mungkin akan ada sedikit informasi di trek) kurang). Karena itu, sinyal analog tidak dapat disimpan, Anda harus berurusan dengan digitalisasi. Pendekatan utama untuk digitalisasi sinyal analog adalah modulasi kode pulsa, yang akan dibahas pada bagian ini. PCM terdiri dari tiga tahap: diskritisasi, kuantisasi dan pengkodean. Mari kita menganalisis secara singkat apa yang terjadi pada masing-masing dari mereka.
Diskretisasi
Jadi, kami memiliki fungsi amplitudo terhadap waktu. Jika seseorang memiliki pertanyaan, di mana frekuensinya, maka ia tersembunyi di balik tikungan grafik fungsi. Dia belum terlihat, tetapi nanti kita akan menariknya keluar. Karena kita berbicara tentang sinyal analog, fungsinya kontinu dan didefinisikan pada seluruh rangkaian argumen yang memungkinkan (bilangan real mana pun dari nol hingga akhir lintasan). Artinya, kita tahu nilai fungsi setiap saat, dan kami memiliki banyak momen. Kami jelas tidak perlu begitu banyak, jadi ambil saja beberapa himpunan bagian diskrit. Untuk melakukan ini, kami akan menyimpan nilai sinyal pada interval kecil yang tetap. Itu harus cukup kecil sehingga kita tidak mendengar perbedaan di telinga, tetapi cukup besar untuk tidak menyimpan terlalu banyak, karena ini juga tidak diinginkan.
Bahkan, ketika mendigitalkan, itu bukan interval yang ditetapkan, tetapi frekuensi, yang disebut "frekuensi pengambilan sampel." Tergantung pada tugasnya, frekuensi sampling dapat dari 8 kHz di telepon ke beberapa ribu kHz di peralatan audio profesional. Musik untuk mendengarkan biasa di luar studio rekaman biasanya disimpan pada frekuensi 44,1 kHz atau 48 kHz.
Kuantisasi
Berkat diskritisasi, kami sekarang memiliki banyak titik alih-alih grafik fungsi kontinu, tetapi kami masih tidak dapat bekerja dengannya, kami perlu lebih merusak suaranya. Fungsi awal amplitudo terhadap waktu membandingkan amplitudo kontinum dengan waktu kontinum. Seiring waktu, kami menemukan jawabannya, dan sekarang kami perlu membuat sesuatu dengan amplitudo, karena nilai saat ini tersebar di seluruh rangkaian bilangan real terlalu kacau untuk kami simpan tanpa masalah. Misalnya, di antara mereka, pasti, ada yang tidak rasional yang tidak bisa kita simpan dengan cara apa pun tanpa pembulatan.
Kuantisasi adalah proses di mana kami membulatkan amplitudo ke nilai dari set yang dipilih sebelumnya. Tentu saja, kami ingin jumlah amplitudo menjadi kekuatan dua. Untuk trek audio biasa, kuantisasi 16-bit digunakan, yaitu, jumlah amplitudo akan 65.536 (2 hingga 16 derajat). Rekaman suara profesional dapat dilakukan dengan akurasi yang lebih besar, tetapi hanya sedikit orang yang dapat membedakan kuantisasi 16-bit dari 24-bit. Jadi, kami mengambil kekuatan dua, mengambil sekelompok amplitudo integer dan menyebutnya tingkat kuantisasi. Maka akan mungkin untuk mengatakan bahwa sinyal dikuantisasi di atas level 65.536 (terdengar otoritatif, kan?). Setiap amplitudo dibulatkan ke salah satu level, yang pada akhirnya memungkinkan Anda untuk menyimpan nilainya dalam 16 bit, dan dengan begitu rekaman seperti itu tidak dapat dibedakan dari suara kontinu analog.
Sebagai ilustrasi, Anda dapat melihat gambar di bawah ini, atau menghasilkan gambar Anda sendiri dengan Python (kodenya bahkan lebih rendah). Bagian kanan atas ilustrasi menunjukkan lima tingkat kuantisasi. Artinya, trek hanya akan memiliki lima level volume.
Beberapa contohimport numpy as np import matplotlib.pyplot as plt import math as m def f(x): return m.sin(x) q = 1/2
Coding
Pada tahap pengkodean, kami menyimpan hasil dari langkah-langkah sebelumnya dalam bentuk yang dapat dimengerti. Semua tindakan sebelum ini biasanya dilakukan oleh peralatan khusus, tetapi kami ingin memiliki file di komputer atau array di memori di mana akan ada amplitudo. Oleh karena itu, pada tahap ini, sinyal peralatan diubah menjadi array angka, yang akan kita sebut PCM (modulasi kode pulsa) di masa depan. Indeks-indeksnya adalah waktu kondisional (indeks interval setelah pengambilan sampel), dan amplitudo disimpan di dalamnya, dibulatkan menjadi bilangan bulat pada tahap kuantisasi.
Transformasi Fourier
Awalnya, kami memiliki gelombang mekanis dan keinginan untuk mendigitalkannya, tetapi sekarang kami memiliki sinyal digital dan keinginan untuk mendapatkan frekuensi darinya. Yang diinginkan dapat dicapai dengan menggunakan transformasi Fourier. Untuk jaga-jaga, saya akan menceritakan kembali nilai yang diterapkan dalam masalah ini. Transformasi Fourier memungkinkan Anda untuk mengambil fungsi apa pun dan menguraikannya menjadi jumlah sinus dan cosinus. Kami tertarik pada ini, karena sinusoid dan gelombang kosinus adalah tentang getaran, dan suara adalah tentang getaran. Artinya, menggunakan transformasi Fourier, Anda bisa mendapatkan komponen osilasi yang kompleks, mencari tahu amplitudo dan frekuensinya, hanya dengan melihat koefisien apa yang ada di depan argumen sinus dan sinus (atau kosinus). Misalnya, ada gelombang seperti itu.
GelombangFaktanya, kita tahu bahwa itu didefinisikan oleh fungsi 10sin (3x) + sin (x) + 4sin (4x) + 20sin (2x), tetapi sekarang, dan gelombang suara nyata terdiri dari berbagai istilah seperti itu, dan kami ingin dapat bekerja dengannya. Jadi, mari kita jalankan fungsi ini melalui transformasi Fourier menggunakan program
FourierScope dan lihat spektrum amplitudo.
Spektrum amplitudoInilah yang terlihat seperti empat sinus. Sangat mudah untuk melihat bahwa grafik sesuai dengan koefisien sinus dan argumennya.
Harus diklarifikasi bahwa sebenarnya itu adalah demonstrasi kekuatan bukan dari transformasi Fourier itu sendiri, tetapi versi diskritnya, cocok untuk sinyal yang melalui modulasi kode pulsa dengan semua diskritisasi dan kuantisasi. Akan berlebihan untuk menyajikan sebuah algoritma untuk transformasi Fourier diskrit, jadi mari kita sepakati fakta bahwa ada hal yang disebut DFT, serta modifikasinya, fast Fourier transform (FFT). Dalam hal ini, pengertian FFT yang diterapkan adalah sebagai berikut: algoritma menerima sepotong PCM pada input dan memberikan array yang berisi amplitudo, dan tempat frekuensi adalah indeks. Ini adalah masalah tempat sampah frekuensi, bukan hanya frekuensi, karena konversi itu terpisah. Bahkan, naif untuk berharap bahwa Anda dapat mengacaukan sinyal di seluruh artikel, dan kemudian hanya mendapatkan frekuensi tanpa masalah dan ketidakakuratan. Bahkan, nampan frekuensi adalah sejumlah frekuensi yang FFT tidak dapat membedakan satu sama lain.
Perlu dicatat bahwa FFT sering dieja salah ketika menulis ulang suatu algoritma dari buku dan artikel. Di bawah ini adalah kode yang lebih tepat untuk bekerja dengan FFT, yang persis seperti yang kami harapkan dari para peserta dalam solusi mereka.
import "github.com/mjibson/go-dsp/fft" ... blocksCount := len(pcm) / fftWindowSize for i := 0; i < blocksCount; i++ { complexArray := fft.FFTReal(pcm[i*fftWindowSize : i*fftWindowSize+fftWindowSize]) // use complexArray... }
Teknologi modern memungkinkan Anda untuk menulis transformasi Fourier cepat hanya dalam beberapa baris. FFT digunakan untuk segmen ukuran fftWindowSize dan mengembalikan array angka kompleks, yang akan kita gunakan untuk sidik jari di masa depan.
Secara umum, transformasi Fourier adalah tempat paling tipis di seluruh masalah. Pertama, ukuran bin adalah $ \ frac {frequency \ sampling} {size \ window} $. Dengan demikian, Anda dapat memperbesar jendela dan mendapatkan lebih banyak frekuensi, yang bagus, tetapi tentu saja, memiliki konsekuensi negatif. Peningkatan ukuran jendela mengarah pada fakta bahwa kami menganalisis PCM pada interval besar dan kehilangan suara dalam durasi singkat. Dalam keadaan yang berbeda, ini dapat berulang kali memperburuk program jika suara pendek adalah bagian dari komposisi, atau dapat meningkatkan jika itu hanya suara. Atau mungkin tidak memengaruhi apa pun. Dalam situasi yang sulit seperti itu, programmer harus bertindak tegas: mengambil angka yang bagus, seperti $ 2 ^ 9 $ atau $ 2 ^ {10} $, dan mencoba untuk tidak repot dengan seluk-beluk di mana ini tidak diperlukan. Cukup untuk menyelesaikan masalah, tetapi dalam aplikasi serius Anda masih harus menggunakan beberapa jendela Hamming dan banyak lagi untuk dipikirkan.
Sidik jari
Tugasnya adalah mempelajari cara memiliki hash yang dapat dipetakan ke trek dan yang tidak sensitif terhadap perubahan, memiliki frekuensi dan amplitudo komposisi. Mereka bisa sangat berbeda: sedikit suara, pergeseran semua frekuensi, memainkan lagu lain secara paralel, dan sebagainya. Anda juga perlu mempertimbangkan bahwa basis data dapat secara bersamaan memuat banyak trek serupa yang perlu dibedakan satu sama lain. Atau mungkin semua trek akan berbeda, dan masalahnya bukan menentukan mana yang lebih cocok, tetapi untuk memahami bahwa tidak ada yang cocok. Secara umum, ada ruang lingkup tertentu untuk kreativitas.
Anda dapat mencetak dengan berbagai cara. Katakanlah membuat hash dalam bentuk daftar beberapa indikator berbeda. Di antara mereka mungkin, misalnya, jumlah rata-rata penyeberangan sinyal nol, BPM, nilai frekuensi rata-rata. Saya melakukan ini di versi
Musicbrainz sebelumnya, dan masalah pendekatan ini ditulis di
sini . Dan Anda dapat mempertimbangkan konsep yang lebih abstrak, seperti ritme, menganalisis trek menggunakan algoritma EM (
artikel ). Secara umum, kebebasan berekspresi sepenuhnya. Sayangnya, sebagian besar algoritma yang diusulkan, tampaknya, tidak memiliki implementasi publik, jadi hanya mengambil dan membandingkannya tidak akan berhasil.
Implementasi arus utama dijelaskan dalam artikel
ini . Sangat menyenangkan bahwa Anda dapat mengimplementasikan algoritma ini dalam beberapa baris. Misalnya, dalam artikel asli, diusulkan untuk membagi frekuensi menjadi 6 interval, temukan amplitudo maksimum di masing-masing, ambil rata-rata dari keenam dan simpan nampan yang lebih tinggi dari rata-rata, tetapi banyak implementasi lain yang mungkin.
var freqBins = [...]int16{40, 80, 120, 180, 300} func getKeyPoints(frame []freq_domain) int { highScores := make([]float64, len(freqBins)) recordPoints := make([]uint, len(freqBins)) for bin := freqBins[0]; bin < freqBins[len(freqBins)-1]; bin++ { magnitude := frame[bin] binIdx := 0 for freqBins[binIdx] < bin { binIdx++ } if magnitude > highScores[binIdx] { highScores[binIdx] = magnitude recordPoints[binIdx] = (uint)(bin) } } return hash(recordPoints) }
Fungsi di atas mengimplementasikan algoritma sidik jari. Pada akhirnya, array frekuensi (atau lebih tepatnya, nampan) dilewatkan ke fungsi hash (), yang seharusnya mengubah array beberapa angka menjadi satu angka. Anda dapat melakukan ini dengan cara yang sesuai, Anda bahkan dapat mencoba menggunakan md5 (walaupun ini adalah ide yang buruk).
Tentang pengujian
Beberapa kasus uji disiapkan:- Pretest normal dengan satu trek. Sampel asli dan benar-benar bertepatan.
- Pretest lain dengan dua lagu. Dokumen asli bertepatan dengan sampel.
- Jumlah trek yang sedikit lebih besar diindeks, semua dicari secara bergantian.
- Sejumlah besar lagu dimuat, mereka dicari, tetapi setelah downsampling.
- Track diindeks setelah downsampling, yang asli dicari.
- Mengindeks beberapa trek serupa, mencari yang serupa, tetapi tidak dalam database.
- Beberapa trek diindeks, mereka dicari, tetapi dengan noise.
Beberapa tautan menarik
https://metacpan.org/pod/Audio::Ofa::Utilhttps://www.researchgate.net/publication/228347102_A_Review_of_Audio_Fingerprintinghttp://www.freshmeat.net/projects/songprinthttps://link.springer.com/article/10.1007/s11265-005-4152-2https://github.com/acoustid/chromaprinthttps://laplacian.wordpress.com/2009/01/10/how-shazam-works/