كيفية حل مشكلة التعرف على الصوت على GO

في الآونة الأخيرة ، شاركت BI.ZONE في مؤتمر HighLoad ++. من الواضح أننا وصلنا إلى هناك ليس فقط للتحديق في مواقف الآخرين ، لكننا جلبنا شيئًا مثيرًا للاهتمام. قام الموظفون من مختلف الإدارات في الشركة بإعداد المهام لضيوف المؤتمر ، والتي قدمنا ​​من خلالها جوائز. كانت إحدى مهام Golang مكرسة للتعرف على الصوت. سألنا مؤلفها أن يقول عنها.

بيان المشكلة

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

كيفية تسجيل الصوت

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

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

أخذ العينات

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

في الواقع ، عند الرقمنة ، لا يتم تعيين الفاصل الزمني ، ولكن التردد الذي يسمى "تردد أخذ العينات". اعتمادًا على المهام ، يمكن أن يتراوح تردد أخذ العينات من 8 كيلو هرتز في الهواتف إلى عدة آلاف كيلو هرتز في أجهزة الصوت الاحترافية. عادة ما يتم تخزين الموسيقى للاستماع العادي خارج استوديوهات التسجيل على تردد 44.1 كيلو هرتز أو 48 كيلو هرتز.

تكميم

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

التقدير الكمي عبارة عن عملية يتم خلالها تقريب السعات إلى القيم من مجموعة محددة مسبقًا. بالطبع ، نريد أن يكون عدد السعات قوة اثنين. بالنسبة للمسارات الصوتية العادية ، يتم استخدام القياس الكمي 16 بت ، أي أن عدد السعات سيكون 65 536 (من 2 إلى 16 درجة). يمكن إجراء تسجيل صوتي احترافي بدقة أكبر ، لكن قلة من الأشخاص عن طريق الأذن يمكنهم التمييز بين تكمي 16 بت و 24 بت. لذلك ، نحن نأخذ قوة اثنين ، نأخذ مجموعة من السعات الصحيحة ونطلق عليها مستويات تكميم. بعد ذلك ، سيكون من الممكن القول بأن الإشارة يتم قياسها كمياً على أكثر من 65 536 مستوى (الأصوات بشكل صحيح ، أليس كذلك؟). يتم تقريب كل سعة إلى أحد المستويات ، مما يسمح لك في نهاية المطاف بتخزين قيمته في 16 بت ، وعن طريق الأذن ، لا يمكن تمييز هذا التسجيل من الصوت المستمر التناظري.

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


بعض الأمثلة

import numpy as np import matplotlib.pyplot as plt import math as m def f(x): return m.sin(x) q = 1/2 #      k = 0 #      1/2  1/4 vf = np.vectorize(f) orig_f = vf(np.arange(0, 4 * m.pi, 0.001)) quanted_f = q * np.round(orig_f/q + k) plt.plot(orig_f) plt.plot(quanted_f) 

الترميز

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

تحويل فورييه

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


الموجة

في الواقع ، نحن نعرف أنه يتم تعريفها بواسطة الدالة 10sin (3x) + sin (x) + 4sin (4x) + 20sin (2x) ، ولكن هذا الآن ، وموجة الصوت الحقيقية تتكون من عدد لا يحصى من هذه المصطلحات ، ونود أن نكون قادرين على العمل معها. لذلك ، لنقم بتشغيل هذه الوظيفة من خلال تحويل فورييه باستخدام برنامج FourierScope وإلقاء نظرة على طيف الاتساع.


طيف السعة

هذا هو ما تبدو عليه أربع جيبات. من السهل أن نرى أن الرسم البياني يتوافق مع معاملات الجيب والجدل الخاص بها.

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

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

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

التكنولوجيا الحديثة تسمح لك بكتابة تحويل فورييه السريع في بضعة أسطر. يستخدم FFT لشرائح بحجم fftWindowSize وإرجاع مجموعة من الأرقام المعقدة ، والتي سوف نستخدمها في المستقبل لبصمات الأصابع.

بشكل عام ، فإن تحويل فورييه هو أنحف مكان في المشكلة برمتها. أولاً ، حجم الصندوق هو $ \ frac {frequency \ sampling} {size \ window} $. وفقًا لذلك ، يمكنك تكبير النافذة والحصول على مزيد من الترددات ، وهو أمر لطيف ، ولكن ، بالطبع ، له عواقب سلبية. تؤدي الزيادة في حجم النافذة إلى قيامنا بتحليل PCM على فترات زمنية كبيرة وفقدان الأصوات لمدة قصيرة. في ظروف مختلفة ، يمكن أن يؤدي ذلك إلى تفاقم البرنامج بشكل متكرر إذا كانت الأصوات القصيرة جزءًا من التكوين ، أو يمكن أن تتحسن إذا كانت مجرد ضوضاء. أو ربما لا يؤثر على أي شيء على الإطلاق. في مثل هذه الحالة الصعبة ، يجب أن يتصرف المبرمج بشكل حاسم: خذ بعضًا من الأرقام الجيدة ، مثل $ 2 ^ 9 $ أو $ 2 ^ {10} $ ، وحاول ألا تهتم بالتعقيدات عندما لا يكون ذلك مطلوبًا. يكفي لحل المشكلة ، ولكن في تطبيق جدي لا يزال عليك استخدام بعض نافذة Hamming وأكثر من ذلك بكثير للتفكير.

البصمات

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

يمكنك أن تأخذ الطباعة بطرق مختلفة. دعنا نقول جعل التجزئة في شكل قائمة من عدة مؤشرات مختلفة. قد يكون من بينها ، على سبيل المثال ، متوسط ​​عدد معابر إشارة الصفر ، BPM ، متوسط ​​قيم التردد. لقد فعلت ذلك في الإصدارات السابقة من Musicbrainz ، وتتم كتابة مشاكل هذا النهج هنا . ويمكنك التفكير في المزيد من المفاهيم المجردة ، مثل الإيقاع ، وتحليل المسار باستخدام خوارزمية EM ( مقالة ). بشكل عام ، حرية التعبير كاملة. لسوء الحظ ، فإن معظم الخوارزميات المقترحة ، على ما يبدو ، ليس لديها تطبيق عام ، لذلك لن يعمل أخذها ومقارنتها.

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

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

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

عن الاختبار

تم إعداد عدة حالات اختبار:

1. الاختبار القبلي العادي مع مسار واحد. الأصلي والعينة تزامن تماما.
2. الاختبار القبلي الآخر مع مسارين. تزامنت النسخ الأصلية مع العينات.
3. يتم فهرسة عدد أكبر قليلاً من المقطوعات ، ويتم البحث في جميعها بالتناوب.
4. يتم تحميل عدد كبير من المسارات ، يتم البحث عنها ، ولكن بعد الاختزال.
5. تتم فهرسة المسارات بعد الاختزال ، ويتم البحث عن المسارات الأصلية.
6. فهرستها عدة مسارات مماثلة ، وتبحث عن مماثلة ، ولكن ليس في قاعدة البيانات.
7. تتم فهرسة عدة مسارات ، يتم البحث عنها ، ولكن مع وجود ضوضاء.

بعض الروابط المثيرة للاهتمام

https://metacpan.org/pod/Audio::Ofa::Util
https://www.researchgate.net/publication/228347102_A_Review_of_Audio_Fingerprinting
http://www.freshmeat.net/projects/songprint
https://link.springer.com/article/10.1007/s11265-005-4152-2
https://github.com/acoustid/chromaprint
https://laplacian.wordpress.com/2009/01/10/how-shazam-works/