كيف يعمل تطبيق Shazam؟ خوارزميات التعرف على الموسيقى وبصمات الأصابع والمعالجة

تسمع أغنية مألوفة في النادي أو المطعم. لقد استمعت إلى هذه الأغنية منذ فترة طويلة ألف مرة ، وعاطفية الأغنية تمس قلبك حقًا. أنت تريد بشدة أن تحبه غدًا ، لكن لا يمكنك تذكر اسمه! لحسن الحظ ، في عالمنا المستقبلي المذهل ، لديك هاتف مثبت عليه برنامج التعرف على الموسيقى ، ويتم حفظك. يمكنك الاسترخاء ، لأن البرنامج أخبرك باسم الأغنية ، وأنت تعلم أنه يمكنك سماعها مرارًا وتكرارًا حتى تصبح جزءًا منك ... أو تمل منها.

لقد منحتنا تقنيات الهاتف المحمول ، جنبًا إلى جنب مع التقدم الهائل في معالجة الإشارات الصوتية ، لمطوري الخوارزميات القدرة على إنشاء أدوات التعرف على الموسيقى. يعد Shazam أحد أشهر تطبيقات التعرف على الموسيقى. إذا التقطت 20 ثانية من أغنية ، بغض النظر عما إذا كانت مقدمة أو مقطوعة أو جوقة ، فسيقوم بإنشاء بصمة للعينة المسجلة ، واستشارة قاعدة البيانات ، واستخدام خوارزمية التعرف على الموسيقى لإخبارك بالضبط بالأغنية التي تستمع إليها .

لكن كيف يعمل Shazam؟ تم الكشف عن خوارزمية Shazam للعالم من قبل مخترعها Avery Li-Chung Wang في عام 2003. في هذه المقالة سوف نستعرض أساسيات خوارزمية التعرف على الموسيقى الخاصة بـ Shazam.

التناظرية إلى الرقمية - أخذ عينات إشارة

ما هو الصوت حقا؟ هل هي نوع من المواد الصوفية التي لا يمكننا لمسها ولكنها تطير في آذاننا وتجعلنا نسمع الأشياء؟

بالطبع ، هذا ليس هو الحال تماما. نحن نعلم أنه في الواقع ، الصوت هو اهتزاز ينتشر كموجة ميكانيكية للضغط والإزاحة ، عبر وسط مثل الهواء أو الماء. عندما يصل هذا الاهتزاز إلى آذاننا ، وخاصة طبلة الأذن ، فإنه يحرك العظام الصغيرة التي تنقل الاهتزاز إلى خلايا الشعر الصغيرة في أعماق أذننا الداخلية. أخيرًا ، تنتج خلايا الشعر الصغيرة نبضات كهربائية تنتقل إلى دماغنا عبر عصب الأذن السمعي.

تحاكي أجهزة التسجيل هذه العملية عن كثب ، باستخدام ضغط الموجة الصوتية لتحويلها إلى إشارة كهربائية. الموجة الصوتية الفعلية في الهواء هي إشارة ضغط مستمر. في الميكروفون ، يترجم المكون الكهربائي الأول الذي يواجه هذه الإشارة إلى إشارة جهد تناظرية - مرة أخرى ، مستمرة. هذه الإشارة المستمرة ليست مفيدة جدًا في العالم الرقمي ، لذا قبل أن تتم معالجتها ، يجب ترجمتها إلى إشارة منفصلة يمكن تخزينها رقميًا. يتم ذلك عن طريق التقاط قيمة رقمية تمثل اتساع الإشارة.

ينطوي التحويل على تكميم المدخلات ، ويتسبب بالضرورة في قدر ضئيل من الخطأ. لذلك ، بدلاً من التحويل الفردي ، يقوم المحول التناظري إلى الرقمي بإجراء العديد من التحويلات على أجزاء صغيرة جدًا من الإشارة - وهي عملية تُعرف باسم أخذ العينات

تخبرنا نظرية نيكويست شانون ما هو معدل أخذ العينات الضروري لالتقاط تردد معين في إشارة مستمرة. على وجه الخصوص ، لالتقاط جميع الترددات التي يمكن أن يسمعها الإنسان في إشارة صوتية ، يجب علينا أخذ عينات من الإشارة بتردد ضعف نطاق السمع البشري. يمكن للأذن البشرية الكشف عن ترددات تتراوح بين 20 هرتز و 20000 هرتز تقريبًا. نتيجة لذلك ، يتم تسجيل الصوت غالبًا بمعدل عينات يبلغ 44100 هرتز. هذا هو معدل أخذ العينات للأقراص المضغوطة ، وهو أيضًا المعدل الأكثر استخدامًا مع صوت MPEG-1 (VCD ، SVCD ، MP3). (تم اختيار هذا المعدل المحدد في الأصل بواسطة Sony لأنه يمكن تسجيله على معدات فيديو معدلة تعمل إما بمعدل 25 إطارًا في الثانية (PAL) أو 30 إطارًا في الثانية (باستخدام مسجل فيديو NTSC أحادي اللون) ويغطي النطاق الترددي 20000 هرتز الذي يعتقد أنه ضروري تطابق معدات التسجيل التناظرية الاحترافية في ذلك الوقت.) لذلك ، عند اختيار تردد العينة المطلوب تسجيلها ، ربما ترغب في الانتقال مع 44100 هرتز.

التسجيل - التقاط الصوت

يعد تسجيل إشارة صوتية عينة أمرًا سهلاً. نظرًا لأن بطاقات الصوت الحديثة تأتي بالفعل مع محولات من التناظرية إلى الرقمية ، فما عليك سوى اختيار لغة برمجة ، والعثور على مكتبة مناسبة ، وتعيين تردد العينة ، وعدد القنوات (عادةً أحادية أو ستيريو) ، وحجم العينة (مثل عينات 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.)

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

المجال الزمني ومجال التردد

ما لدينا في مجموعة البايت هذه هو الإشارة المسجلة في المجال الزمني. تمثل إشارة المجال الزمني تغير اتساع الإشارة بمرور الوقت.

في أوائل القرن التاسع عشر ، توصل جان بابتيست جوزيف فورييه إلى اكتشاف رائع مفاده أن أي إشارة في المجال الزمني تعادل مجموع عدد (ربما لانهائي) من الإشارات الجيبية البسيطة ، بالنظر إلى أن كل مكون جيبي له تردد معين ، وسعة ، والمرحلة. تُعرف سلسلة الجيوب التي تشكل معًا إشارة المجال الزمني الأصلية باسم سلسلة فورييه.

بمعنى آخر ، من الممكن تمثيل أي إشارة مجال زمني ببساطة عن طريق إعطاء مجموعة من الترددات والسعات والمراحل المقابلة لكل جيبية تشكل الإشارة. يُعرف تمثيل الإشارة هذا باسم مجال التردد. في بعض النواحي ، يعمل مجال التردد كنوع من بصمات الأصابع أو التوقيع لإشارة المجال الزمني ، مما يوفر تمثيلًا ثابتًا للإشارة الديناميكية.

يوضح الرسم المتحرك التالي سلسلة فورييه لموجة مربعة 1 هرتز ، وكيف يمكن إنشاء موجة مربعة (تقريبية) من المكونات الجيبية. تظهر الإشارة في المجال الزمني أعلاه ، ومجال التردد أدناه.

إن تحليل إشارة في مجال التردد يبسط أشياء كثيرة إلى حد كبير. إنه أكثر ملاءمة في عالم معالجة الإشارات الرقمية لأن المهندس يمكنه دراسة الطيف (تمثيل الإشارة في مجال التردد) وتحديد الترددات الموجودة وأيها مفقودة. بعد ذلك ، يمكن للمرء أن يقوم بفلترة بعض الترددات أو زيادتها أو تقليلها ، أو مجرد التعرف على النغمة الدقيقة من الترددات المحددة.

تحويل فورييه المنفصل

لذلك نحن بحاجة إلى إيجاد طريقة لتحويل إشارتنا من المجال الزمني إلى مجال التردد. هنا نطلب المساعدة من تحويل فورييه المنفصل (DFT). DFT هي منهجية رياضية لإجراء تحليل فورييه على إشارة منفصلة (عينة). إنه يحول قائمة محدودة من العينات المتباعدة بشكل متساوٍ لوظيفة ما إلى قائمة معاملات تركيبة محدودة من أشباه الجيوب المعقدة ، مرتبة حسب تردداتها ، من خلال النظر في ما إذا كانت تلك الجيوب الأنفية قد تم أخذ عينات منها بنفس المعدل.

يعد تحويل فورييه السريع (FFT) أحد الخوارزميات العددية الأكثر شيوعًا لحساب DFT. تعد خوارزمية Cooley-Tukey أكثر أشكال FFT شيوعًا إلى حد بعيد. هذه خوارزمية فرق تسد تقسم بشكل متكرر DFT إلى العديد من DFTs الأصغر. في حين أن تقييم DFT يتطلب مباشرة عمليات O ( n 2 ) ، مع Cooley-Tukey FFT يتم حساب نفس النتيجة في عمليات O ( n log n ) .

ليس من الصعب العثور على مكتبة مناسبة لـ FFT. فيما يلي عدد قليل منهم:

• ج - FFTW
• C ++ - EigenFFT
• جافا - JTransform
• بايثون - NumPy
• روبي - روبي FFTW3 (واجهة FFTW)

يوجد أدناه مثال على دالة FFT مكتوبة بلغة Java. (تأخذ 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 هو أننا نفقد قدرًا كبيرًا من المعلومات حول التوقيت. (على الرغم من أنه يمكن تجنب ذلك نظريًا ، إلا أن الأداء مرتفع للغاية.) بالنسبة لأغنية مدتها ثلاث دقائق ، نرى جميع الترددات وحجمها ، لكن ليس لدينا دليل عندما ظهرت في الأغنية. لكن هذه هي المعلومات الأساسية التي تجعل الأغنية على ما هي عليه! بطريقة ما نحتاج إلى معرفة النقطة الزمنية التي ظهر فيها كل تردد.

لهذا السبب نقدم نوعًا من النافذة المنزلقة ، أو قطعة من البيانات ، ونحول هذا الجزء فقط من المعلومات. يمكن تحديد حجم كل قطعة بعدة طرق مختلفة. على سبيل المثال ، إذا سجلنا الصوت ، في ستريو ، بعينات 16 بت ، عند 44100 هرتز ، فإن ثانية واحدة من هذا الصوت ستكون 44100 عينة * 2 بايت * قناتان ≈ 176 كيلو بايت. إذا اخترنا 4 كيلو بايت لحجم قطعة ، سيكون لدينا 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.70 هرتز) وعالي C - C8 (4،186.01 هرتز). هذه فترة زمنية ضخمة يجب تغطيتها. لذلك بدلاً من تحليل النطاق الترددي بأكمله مرة واحدة ، يمكننا اختيار عدة فترات زمنية أصغر ، يتم اختيارها بناءً على الترددات الشائعة للمكونات الموسيقية المهمة ، وتحليل كل منها على حدة. على سبيل المثال ، قد نستخدم الفواصل الزمنية التي اختارها هذا الرجل لتنفيذه لخوارزمية Shazam. هذه هي 30 هرتز - 40 هرتز ، 40 هرتز - 80 هرتز و 80 هرتز - 120 هرتز للنغمات المنخفضة (تغطي جيتار الجهير ، على سبيل المثال) ، و 120 هرتز - 180 هرتز و 180 هرتز - 300 هرتز للنغمات المتوسطة والعالية (تغطي الغناء ومعظم الآلات الأخرى).

الآن في كل فترة زمنية ، يمكننا ببساطة تحديد التردد بأكبر قدر. تشكل هذه المعلومات توقيعًا لهذه القطعة من الأغنية ، ويصبح هذا التوقيع جزءًا من بصمة الأغنية ككل.

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

لاحظ أنه يجب أن نفترض أن التسجيل لم يتم في ظروف مثالية (على سبيل المثال ، "غرفة الصم") ، ونتيجة لذلك يجب علينا تضمين عامل الزغب. يجب أن يؤخذ تحليل عامل الزغب على محمل الجد ، وفي النظام الحقيقي ، يجب أن يكون للبرنامج خيار لتعيين هذه المعلمة بناءً على شروط التسجيل.

لتسهيل البحث الصوتي ، يصبح هذا التوقيع هو المفتاح في جدول التجزئة. القيمة المقابلة هي الوقت الذي ظهرت فيه مجموعة الترددات هذه في الأغنية ، جنبًا إلى جنب مع معرف الأغنية (عنوان الأغنية والفنان). فيما يلي مثال على كيفية ظهور هذه السجلات في قاعدة البيانات.

إذا قمنا بتشغيل مكتبة كاملة من الأغاني من خلال عملية تحديد الموسيقى هذه ، فيمكننا إنشاء قاعدة بيانات ببصمة كاملة لكل أغنية في المكتبة.

خوارزمية الموسيقى: تحديد الأغنية

لتحديد الأغنية التي يتم تشغيلها حاليًا في النادي ، نقوم بتسجيل الأغنية بهاتفنا ، وتشغيل التسجيل من خلال عملية البصمة الصوتية نفسها كما هو مذكور أعلاه. ثم يمكننا البدء في البحث في قاعدة البيانات عن مطابقة علامات التجزئة.

كما يحدث ، ستتوافق العديد من علامات التجزئة مع معرف الموسيقى لأغاني متعددة. على سبيل المثال ، قد تكون بعض الأغنيات A تبدو تمامًا مثل قطعة من الأغنية E. بالطبع ، هذا ليس مفاجئًا - لقد استعار الموسيقيون دائمًا اللعقات والريفات من بعضهم البعض ، وفي هذه الأيام يقوم المنتجون بتجربة الأغاني الأخرى كلها الوقت. في كل مرة نقوم فيها بمطابقة علامة التجزئة ، يقل عدد المطابقات المحتملة ، ولكن من المحتمل أن هذه المعلومات وحدها لن تقصر المطابقة على أغنية واحدة. هناك شيء آخر نحتاج إلى التحقق منه باستخدام خوارزمية التعرف على الموسيقى ، وهو التوقيت.

قد يكون النموذج الذي سجلناه في النادي من أي نقطة في الأغنية ، لذلك لا يمكننا ببساطة مطابقة الطابع الزمني للتجزئة المتطابقة مع الطابع الزمني للعينة. ومع ذلك ، باستخدام تجزئات متطابقة متعددة ، يمكننا تحليل التوقيت النسبي للمباريات ، وبالتالي زيادة اليقين.

على سبيل المثال ، إذا نظرت في الجدول أعلاه ، فسترى أن علامة التجزئة 30 51 99 121 195 تتوافق مع كل من Song A و Song E. إذا قمنا بعد ثانية واحدة بمطابقة التجزئة 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 ، يمكنك أن ترى كيف يمكن لهذا أن يحتوي على تطبيقات تتجاوز مجرد Shazaming تلك الأغنية الحنين إلى الماضي التي يتم تشغيلها على راديو التاكسي. على سبيل المثال ، يمكن أن يساعد في تحديد الانتحال في الموسيقى ، أو معرفة من كان مصدر الإلهام الأولي لبعض رواد موسيقى البلوز أو الجاز أو الروك أو البوب ​​أو أي نوع آخر. ربما تكون التجربة الجيدة هي ملء قاعدة بيانات عينة الأغاني بالموسيقى الكلاسيكية لباخ وبيتهوفن وفيفالدي وفاجنر وشوبان وموزارت ومحاولة إيجاد أوجه التشابه بين الأغاني. قد تعتقد أنه حتى بوب ديلان وإلفيس بريسلي وروبرت جونسون كانوا منتحلين!

لكن ما زلنا لا نستطيع إدانتهم ، لأن الموسيقى هي مجرد موجة نسمعها ونحفظها ونكررها في رؤوسنا ، حيث تتطور وتتغير حتى نسجلها في الاستوديو وننقلها إلى العبقري الموسيقي العظيم التالي.