Shazam nasıl çalışır? Müzik Tanıma Algoritmaları, Parmak İzi ve İşleme

Kulüpte veya restoranda tanıdık bir şarkı duyarsınız. Bu şarkıyı çok uzun zaman önce binlerce kez dinlediniz ve şarkının duygusallığı gerçekten yüreğinize dokunuyor. Umutsuzca yarın kalp atmak istiyorsun ama adını hatırlayamıyorsun! Neyse ki, şaşırtıcı fütüristik dünyamızda, müzik tanıma yazılımının yüklü olduğu bir telefonunuz var ve kurtuldunuz. Rahatlayabilirsiniz, çünkü yazılım size şarkının adını söyledi ve şarkı sizin bir parçanız olana kadar ya da bıkıncaya kadar onu tekrar tekrar duyabileceğinizi bilirsiniz.

Mobil teknolojiler, ses sinyali işlemedeki büyük ilerlemeyle birlikte, algoritma geliştiricilere müzik tanıyıcıları oluşturma yeteneği kazandırdı. En popüler müzik tanıma uygulamalarından biri Shazam'dır. Bir şarkının 20 saniyesini yakalarsanız, ister giriş, ister ayet veya koro olsun, kaydedilen örnek için bir parmak izi oluşturacak, veritabanına başvuracak ve tam olarak hangi şarkıyı dinlediğinizi size söylemek için müzik tanıma algoritmasını kullanacaktır. .

Ama Shazam nasıl çalışır? Shazam'ın algoritması, 2003 yılında mucidi Avery Li-Chung Wang tarafından dünyaya açıklandı. Bu yazıda Shazam'ın müzik tanıma algoritmasının temellerini inceleyeceğiz.

Analogdan Dijitale - Bir Sinyali Örnekleme

Ses gerçekten nedir? Dokunamadığımız ama kulaklarımıza giren ve bir şeyler duymamızı sağlayan bir tür mistik malzeme mi?

Tabii ki, durum tam olarak böyle değil. Gerçekte sesin, hava veya su gibi bir ortam aracılığıyla mekanik bir basınç ve yer değiştirme dalgası olarak yayılan bir titreşim olduğunu biliyoruz. Bu titreşim kulaklarımıza, özellikle kulak zarına geldiğinde, titreşimi iç kulağımızın derinliklerindeki küçük tüy hücrelerine ileten küçük kemikleri hareket ettirir. Son olarak, küçük tüy hücreleri, işitsel kulak siniri yoluyla beynimize iletilen elektriksel uyarılar üretir.

Kayıt cihazları, ses dalgasının basıncını elektrik sinyaline dönüştürmek için kullanarak bu süreci oldukça yakından taklit eder. Havadaki gerçek bir ses dalgası sürekli bir basınç sinyalidir. Bir mikrofonda, bu sinyalle karşılaşan ilk elektrik bileşeni, onu bir analog voltaj sinyaline çevirir - yine sürekli. Bu sürekli sinyal dijital dünyada çok kullanışlı değildir, bu nedenle işlenmeden önce dijital olarak saklanabilen ayrı bir sinyale çevrilmesi gerekir. Bu, sinyalin genliğini temsil eden bir dijital değer yakalanarak yapılır.

Dönüştürme, girdinin nicelleştirilmesini içerir ve zorunlu olarak az miktarda hata getirir. Bu nedenle, tek bir dönüştürme yerine, bir analogdan dijitale dönüştürücü, sinyalin çok küçük parçaları üzerinde birçok dönüştürme gerçekleştirir - örnekleme olarak bilinen bir süreç

Nyquist-Shannon Teoremi bize sürekli sinyalde belirli bir frekansı yakalamak için hangi örnekleme hızının gerekli olduğunu söyler. Özellikle, bir ses sinyalinde bir insanın duyabileceği tüm frekansları yakalamak için, sinyali insan işitme aralığının iki katı bir frekansta örneklemeliyiz. İnsan kulağı kabaca 20 Hz ile 20.000 Hz arasındaki frekansları algılayabilir. Sonuç olarak, ses çoğunlukla 44.100 Hz örnekleme hızında kaydedilir. Bu, Kompakt Disklerin örnekleme hızıdır ve aynı zamanda MPEG-1 sesle (VCD, SVCD, MP3) en yaygın olarak kullanılan hızdır. (Bu özel oran, orijinal olarak Sony tarafından seçilmiştir, çünkü bu, saniyede 25 kare (PAL) veya saniyede 30 kare (bir NTSC monokrom video kaydedici kullanılarak) çalışan değiştirilmiş video ekipmanına kaydedilebilir ve bunun için gerekli olduğu düşünülen 20.000 Hz bant genişliğini kapsayabilir. zamanın profesyonel analog kayıt ekipmanıyla eşleşir.) Bu nedenle, kaydedilmesi gereken örneğin frekansını seçerken muhtemelen 44.100 Hz ile gitmek isteyeceksiniz.

Kayıt - Sesi Yakalama

Örneklenmiş bir ses sinyalini kaydetmek kolaydır. Modern ses kartları zaten analogdan dijitale dönüştürücülerle birlikte geldiğinden, sadece bir programlama dili seçin, uygun bir kitaplık bulun, numunenin frekansını, kanal sayısını (tipik olarak mono veya stereo), numune boyutunu (örneğin 16-bit numuneleri) ayarlayın. ). Ardından ses kartınızdaki satırı herhangi bir giriş akışı gibi açın ve bir bayt dizisine yazın. Java'da bunun nasıl yapılabileceği aşağıda açıklanmıştır:

 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();

Sadece TargetDataLine verileri okuyun. (Bu örnekte, running bayrak başka bir iş parçacığı tarafından durdurulan global bir değişkendir - örneğin, STOP düğmeli GUI'miz varsa.)

 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); }

Zaman Alanı ve Frekans Alanı

Bu bayt dizisinde sahip olduğumuz şey, zaman alanında kaydedilen sinyaldir. Zaman alan sinyali, sinyalin zaman içindeki genlik değişimini temsil eder.

1800'lerin başlarında, Jean-Baptiste Joseph Fourier, zaman alanındaki herhangi bir sinyalin, her bir sinüzoid bileşeninin belirli bir frekansı, genliği, ve faz. Birlikte orijinal zaman alanı sinyalini oluşturan sinüzoid serisi, Fourier serisi olarak bilinir.

Başka bir deyişle, sinyali oluşturan her bir sinüzoide karşılık gelen frekans, genlik ve faz setini basitçe vererek herhangi bir zaman alanı sinyalini temsil etmek mümkündür. Sinyalin bu temsili frekans alanı olarak bilinir. Bazı yönlerden, frekans alanı, dinamik bir sinyalin statik bir temsilini sağlayarak, zaman alanı sinyali için bir parmak izi veya imza türü görevi görür.

Aşağıdaki animasyon, 1 Hz kare dalganın Fourier serisini ve sinüzoidal bileşenlerden (yaklaşık) bir kare dalganın nasıl üretilebileceğini gösterir. Sinyal, yukarıdaki zaman alanında ve aşağıdaki frekans alanında gösterilmektedir.

Frekans alanında bir sinyali analiz etmek, birçok şeyi son derece basitleştirir. Dijital sinyal işleme dünyasında daha uygundur çünkü mühendis spektrumu (frekans alanındaki sinyalin temsili) inceleyebilir ve hangi frekansların mevcut ve hangilerinin eksik olduğunu belirleyebilir. Bundan sonra, filtreleme yapabilir, bazı frekansları artırabilir veya azaltabilir veya sadece verilen frekanslardan tam tonu tanıyabilir.

Ayrık Fourier Dönüşümü

Bu yüzden sinyalimizi zaman alanından frekans alanına dönüştürmenin bir yolunu bulmamız gerekiyor. Burada yardım için Ayrık Fourier Dönüşümünü (DFT) çağırıyoruz. DFT, ayrık (örneklenmiş) bir sinyal üzerinde Fourier analizi gerçekleştirmek için matematiksel bir metodolojidir. Bir fonksiyonun eşit aralıklı örneklerinin sonlu bir listesini, bu sinüzoidlerin aynı oranda örneklenip örneklenmediğini göz önünde bulundurarak, frekanslarına göre sıralanmış, karmaşık sinüzoidlerin sonlu bir kombinasyonunun katsayı listesine dönüştürür.

DFT'nin hesaplanması için en popüler sayısal algoritmalardan biri Fast Fourier dönüşümüdür (FFT). Açık farkla en yaygın olarak kullanılan FFT varyasyonu Cooley-Tukey algoritmasıdır. Bu, bir DFT'yi yinelemeli olarak birçok küçük DFT'ye bölen bir böl ve yönet algoritmasıdır. Bir DFT'yi değerlendirmek doğrudan O( n 2 ) işlemlerini gerektirirken, Cooley-Tukey FFT ile aynı sonuç O( n log n ) işlemlerinde hesaplanır.

FFT için uygun bir kütüphane bulmak zor değil. İşte bunlardan birkaçı:

• C – FFTW
• C++ – EigenFFT
• Java – JTransform
• Python – NumPy
• Ruby – Ruby-FFTW3 (FFTW'ye Arayüz)

Aşağıda Java ile yazılmış bir FFT işlevi örneği verilmiştir. (FFT karmaşık sayıları girdi olarak alır. Karmaşık sayılar ve trigonometrik fonksiyonlar arasındaki ilişkiyi anlamak için Euler formülünü okuyun.)

 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; }

Ve işte FFT analizinden önceki ve sonraki bir sinyal örneği:

Müzik Tanıma: Bir Şarkının Parmak İzi

FFT'nin talihsiz bir yan etkisi, zamanlama hakkında çok fazla bilgiyi kaybetmemizdir. (Teorik olarak bundan kaçınılabilse de, performans ek yükleri muazzamdır.) Üç dakikalık bir şarkı için tüm frekansları ve büyüklüklerini görüyoruz, ancak şarkıda ne zaman göründüklerine dair bir ipucumuz yok. Ama şarkıyı o şarkı yapan anahtar bilgi bu! Bir şekilde, her frekansın hangi zaman noktasında ortaya çıktığını bilmemiz gerekiyor.

Bu nedenle, bir tür kayan pencere veya veri yığını tanıtıyoruz ve bilginin sadece bu bölümünü dönüştürüyoruz. Her parçanın boyutu birkaç farklı şekilde belirlenebilir. Örneğin, sesi stereo olarak 16 bitlik örneklerle 44.100 Hz'de kaydedersek, böyle bir sesin bir saniyesi 44.100 örnek * 2 bayt * 2 kanal ≈ 176 kB olacaktır. Bir yığının boyutu için 4 kB seçersek, şarkının her saniyesinde analiz edilecek 44 veri yığınına sahip oluruz. Bu, ses tanımlaması için gereken ayrıntılı analiz için yeterince iyi bir yoğunluktur.

Şimdi programlamaya dönelim:

 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); }

İç döngüde, zaman alanı verilerini (örnekleri) hayali kısım 0 ile karmaşık bir sayıya koyuyoruz. Dış döngüde, tüm parçaları yineliyoruz ve her biri üzerinde FFT analizi yapıyoruz.

Sinyalin frekans yapısı hakkında bilgi sahibi olduğumuzda, şarkının dijital parmak izini oluşturmaya başlayabiliriz. Bu, tüm Shazam ses tanıma sürecinin en önemli kısmıdır. Buradaki ana zorluk, yakalanan frekanslar okyanusunda hangi frekansların en önemli olduğunu nasıl ayırt edeceğimizdir. Sezgisel olarak, en yüksek genliğe sahip frekansları ararız (genellikle pikler olarak adlandırılır).

Ancak, bir şarkıda güçlü frekans aralığı düşük C - C1 (32.70 Hz) ve yüksek C - C8 (4.186.01 Hz) arasında değişebilir. Bu, kapsanması gereken çok büyük bir aralıktır. Bu nedenle, tüm frekans aralığını bir kerede analiz etmek yerine, önemli müzik bileşenlerinin ortak frekanslarına dayalı olarak seçilen birkaç küçük aralık seçebilir ve her birini ayrı ayrı analiz edebiliriz. Örneğin, bu adamın Shazam algoritmasını uygulaması için seçtiği aralıkları kullanabiliriz. Bunlar, alçak tonlar için (örneğin bas gitarı kapsayan) 30 Hz - 40 Hz, 40 Hz - 80 Hz ve 80 Hz - 120 Hz ve orta ve daha yüksek tonlar için 120 Hz - 180 Hz ve 180 Hz - 300 Hz'dir. (vokalleri ve diğer birçok enstrümanı kapsar).

Şimdi her aralıkta, en yüksek büyüklükteki frekansı basitçe tanımlayabiliriz. Bu bilgi şarkının bu parçası için bir imza oluşturur ve bu imza bir bütün olarak şarkının parmak izinin bir parçası olur.

 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)); }

Kaydın mükemmel koşullarda yapılmadığını (yani “sağır oda”) varsaymamız gerektiğini ve sonuç olarak bir fuzz faktörünü dahil etmemiz gerektiğini unutmayın. Fuzz faktör analizi ciddiye alınmalı ve gerçek bir sistemde program bu parametreyi kayıt koşullarına göre ayarlama seçeneğine sahip olmalıdır.

Sesli aramayı kolaylaştırmak için bu imza, bir karma tablosunun anahtarı haline gelir. Karşılık gelen değer, şarkı kimliği (şarkı adı ve sanatçı) ile birlikte bu frekans grubunun şarkıda göründüğü zamandır. İşte bu kayıtların veritabanında nasıl görünebileceğine dair bir örnek.

Bu müzik tanımlama süreci boyunca bütün bir şarkı kitaplığı çalıştırırsak, kitaplıktaki her şarkının tam parmak izine sahip bir veritabanı oluşturabiliriz.

Müzik Algoritması: Şarkı Tanımlama

Şu anda kulüpte çalmakta olan bir şarkıyı tespit etmek için şarkıyı telefonumuzla kaydediyoruz ve kaydı yukarıdakiyle aynı ses parmak izi sürecinden geçiriyoruz. Ardından, eşleşen hash etiketleri için veritabanını aramaya başlayabiliriz.

Olduğu gibi, karma etiketlerin çoğu, birden fazla şarkının müzik tanımlayıcısına karşılık gelir. Örneğin, A şarkısının bir parçası tam olarak E şarkısının bir parçasına benziyor olabilir. Tabii ki bu şaşırtıcı değil - müzisyenler her zaman birbirlerinden yalamalar ve riffler “ödünç aldılar” ve bu günlerde yapımcılar diğer şarkıların hepsini örnekliyorlar. zaman. Bir hash etiketini her eşleştirdiğimizde, olası eşleşmelerin sayısı azalır, ancak muhtemelen bu bilgi tek başına eşleşmeyi tek bir şarkıya indirgemeyecektir. Müzik tanıma algoritmamızla kontrol etmemiz gereken bir şey daha var, o da zamanlama.

Kulüpte kaydettiğimiz örnek şarkının herhangi bir noktasından olabilir, bu nedenle eşleşen karmanın zaman damgasını örneğimizin zaman damgasıyla eşleştiremeyiz. Bununla birlikte, birden fazla eşleşen hash ile, eşleşmelerin göreceli zamanlamasını analiz edebilir ve bu nedenle kesinliğimizi artırabiliriz.

Örneğin, yukarıdaki tabloya bakarsanız, 30 51 99 121 195 hash etiketinin hem Song A hem de Song E'ye karşılık geldiğini göreceksiniz. Bir saniye sonra, hash 34 57 95 111 200 ile eşleşirsek, bu bir tane daha Şarkı A ile eşleşir, ancak bu durumda hem karmaların hem de zaman farklılıklarının eşleştiğini biliyoruz.

 // 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; } }

Veritabanından kaydedilen şarkıdaki anlar olarak i 1 ve i 2'yi ve şarkıdaki anlar olarak j 1 ve j 2'yi alalım. Aşağıdaki durumlarda zaman farkı eşleşmeli iki eşleşmemiz olduğunu söyleyebiliriz:

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

<span style=font-family: TimesNewRoman;>VE</span>

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

Bu bize şarkıyı başından, ortasından veya sonundan kaydetme esnekliği verir.

Son olarak, kulüpte kaydettiğimiz şarkının her bir anının, aynı şarkının kütüphanemizde stüdyoda kaydedilmiş her bir karşılık gelen anıyla eşleşmesi pek olası değildir. Kayıt, maçlarda bazı hatalara neden olacak çok fazla gürültü içerecek. Bu yüzden, eşleşme listemizden doğru şarkı dışındakileri çıkarmaya çalışmak yerine, en sonunda, eşleşen tüm şarkıları azalan olasılık sırasına göre sıralıyoruz ve favorimiz sıralama listesindeki ilk şarkı.

Baştan aşağı

“Shazam nasıl çalışır?” Sorusuna cevap vermek için. İşte yukarıdan aşağıya tüm müzik tanıma ve eşleştirme sürecine genel bir bakış:

Bu tür bir sistem için veritabanı oldukça büyük olabilir, bu nedenle bir çeşit ölçeklenebilir veritabanı kullanmak önemlidir. İlişkilere özel bir ihtiyaç yoktur ve veri modeli oldukça basit hale gelir, bu nedenle bir tür NoSQL veritabanı kullanmak için iyi bir durumdur.

Shazam Nasıl Çalışır? Artık biliyorsun

Bu tür şarkı tanıma yazılımı, şarkılar arasındaki benzerlikleri bulmak için kullanılabilir. Artık Shazam'ın nasıl çalıştığını anladığınıza göre, bunun taksi radyosunda çalan nostaljik şarkıyı Shazamlamanın ötesinde nasıl uygulamalara sahip olabileceğini görebilirsiniz. Örneğin, müzikteki intihalin belirlenmesine veya blues, caz, rock, pop veya başka herhangi bir türün öncülerinden bazılarının ilk ilham kaynağının kim olduğunu bulmaya yardımcı olabilir. Belki de şarkı örnek veritabanını Bach, Beethoven, Vivaldi, Wagner, Chopin ve Mozart'ın klasik müzikleriyle doldurmak ve şarkılar arasındaki benzerlikleri bulmaya çalışmak iyi bir deney olabilir. Bob Dylan, Elvis Presley ve Robert Johnson'ın bile intihalci olduğunu düşünürdünüz!

Ama yine de onları mahkum edemiyoruz, çünkü müzik sadece kafamızda duyduğumuz, ezberlediğimiz ve tekrarladığımız, biz onu stüdyoda kaydedip bir sonraki büyük müzik dehasına aktarana kadar geliştiği ve değiştiği bir dalgadır.