در این پست قصد دارم به بهانه پیاده سازی سرویس تکراری‌زدایی صوتی (Audio Deduplication) مرور کوتاهی بر اثر انگشت گیری صوتی (Audio Fingerprinting) داشته باشم و داستان کوتاه پیاده‌سازی یکی از الگوریتم‌های تشخیص صدای تکراری برای سرویس‌مان را شرح دهم. شاید مهم‌ترین کاربرد این پست، آشتی دادن بیشتر خوانندگان با اتفاقات سطح پایین تر در الگوریتم‌ها و فرمول‌های ریاضی و مهم‌تر از آن، معرفی برخی منابع برای مطالعه بیشتر باشد.
توجه : به دلیل کم بودن سواد من در این مبحث خاص، انتظار هر نوع اشتباهی را داشته باشید و حتماً اگر موردی دیدید، به من گوشزد کنید تا اصلاح کنم. نکته مهم این است که تلاش کنیم در مباحثی که در آن خبره نیستیم هم ورود کنیم تا حداقل مطالب جدیدتر یاد بگیریم.
در استارت‌آپ پادکستی که در آن مشغول هستم (که به تازگی با دنباله‌روی از Spotify پادکست‌های ویدیویی نیز ارائه می‌دهد)، چند مشکل داریم:
این مشکلات یک راه حل مشترک دارند. کافیست به نحوی مشخصه‌ای در Track پیدا کنیم که منحصر به فرد بوده و بتوان با آن مشخصه، آن Track را جستجو کرد. اگر یک انسان بخواهد این کار را انجام دهد، احتمالاً دنبال کلماتی که در Track گفته می‌شود می‌رود (مثلاً متن شعر) یا به دنبال ریتم یا بیت خاصی از آن که به گوشش برجسته تر می‌آید می‌گردد. اما ماشین چطور؟ اصلاً ماشین چطور یک آهنگ را می‌فهمد؟ ماشین چطور می‌تواند Track تکراری را تشخیص دهد؟
برای اینکه بهتر متوجه شویم میکروفون و بلندگو چطور کار می‌کنند و این داده‌ها چطور در کامپیوتر ذخیره می‌شوند، بد نیست از یک ویدیوی کوتاه کمک بگیریم:
البته دیرین دیرین منظورم نیست. اینجا قرار بود این ویدیو قرار بگیرد که ویرگول علاقه‌ای به نمایش دادن ویدیو‌های یوتوب ندارد!
همانطور که در ویدیو مشخص است، صدا صرفاً به صورت مقدار متغیر دامنه موجیست که در واحد زمان ذخیره می‌شود. البته این صدای آنالوگ (Analog) است. کامپیوتر گزینه مناسبی برای ذخیره و تحلیل مقادیر پیوسته نیست و در عوض این مقادیر را در بازه‌های ثابت و کوتاه مدت نمونه گیری می‌کند (Sampling) و به ازای هر بازه، یک عدد نگهداری می‌کند. بنابراین یک Track به این صورت ذخیره می‌شود:
همانطور که مشاهده می‌کنید، کامپیوتر از یک صوت، این داده‌ها را دارد و به نظر می‌رسد نهایت برداشتی که از آن می‌توان کرد این است که صدا در چه بازه‌هایی بلند است و در چه بازه‌هایی بلند نیست. اما در اصل، این موج بی‌نظم، در حقیقت از حاصل جمع تعداد بسیار زیادی موج با طول موج ثابت بدست آمده و در حقیقت فرمولی وجود دارد که بتوان این موج را به ریز موج‌های سازنده اش شکست. که این کار به عجیبی بدست آوردن شیر و یخ و توت‌فرنگی از اسموتی است!
اگر در دانشگاه ریاضی مهندسی پاس کرده باشید، حتماً با فوریه آشنا هستید. اما چه پاس کرده باشید و چه نه، توصیه می‌کنم ویدیو‌های کانال ۳ آبی ۱ قهوه‌ای (3Blue1Brown) برای سری فوریه و تبدیل فوریه را حتماً قبل از ادامه تماشا کنید تا در جدیدی در زندگی برایتان گشوده شود!
ماجرا از جایی جذاب می‌شود که تبدیل فوریه را روی این آهنگ اجرا کنیم و به جای نمودار دو بعدی بالا، نمودار سه بعدی زیر حاصل شود:
در این نمودار یا طیف‌نگاره (اسپکتروگرام)، محور x زمان است، محور y نشان دهنده فرکانس‌های مختلف ریز موج‌های تولید کننده موج اصلی و در محور z که مقدار آن از تیره به روشن مشخص است، نشان دهنده دامنه آن ریز موج در آن زمان است.
متاسفانه قابلیت نهفتن (embed) یک iframe دیگر نوشته‌های ویرگول وجود ندارد و نمی‌توانید در همین صفحه با این تبدیل بازی کنید ولی توصیه می‌کنم در این صفحه رفته این تبدیل را با میکروفون خودتان تجربه کنید.
این نمودار کاربرد‌های زیادی در زمینه‌های موسیقی، زبانشناسی، سونار (sonar)، رادار، پردازش گفتار، لرزه‌شناسی و سایر موارد دارد. به طور مثال می‌توان با کمک این نمودار، یک موسیقی را ویرایش کرد، یا با کمک آن، گفتار را به متن و با معکوس کردن این روش، متن را به گفتار تبدیل کرد و … اما نکته مهم این نمودار برای کاربرد مورد نظر ما این بود که طیف‌نگاره یک صوت، در صورتی که بلندی صدا کم و زیاد شود، منبع صدا دور شود و بعضی نویز‌ها اضافه شوند، همچنان اشتراکاتی با طیف‌نگاره صوت اصلی دارد. توصیه می‌کنم درستی این جمله را در طیف‌نگاره‌ای که قبلاً معرفی شد، بررسی نمایید.
تا اینجای کار مشخص شد که طیف‌نگاره نامزد مناسبی برای استخراج اثر انگشت است. حالا چالش استخراج یک مجموعه داده حداقلی است که بتوان به کمک آن، یک صوت مشابه به صوت مرجع را با درصدی تحمل خطا پیدا کرد. پس یک مصالحه (trade-off) باید بین حجم داده‌ها، تحمل خطا و دقت انجام شود. مثلاً ممکن است برای یک Track حدود ۵ مگابایتی نیاز باشد ۲۵ مگابایت داده اثر انگشت ذخیره شود که دقت بالایی داشته باشد ولی مطلوب نیست. یا به همین ترتیب ممکن است داده‌ای ذخیره شود که اگر مقدار کمی نویز در آن وجود داشته باشد، تشابه پیدا نشود که این هم مطلوب نیست. یا در بدترین حالت، هر صوتی که ارتباطی با صوت مرجع نداشته باشد، پیدا شود. درصد تحمل خطا به مورد استفاده (use-case) نیز بستگی دارد؛ به طور مثال ممکن است نیاز باشد در یک فیلم که در آن چند نفر در حال صحبت باشند و یک موسیقی دارای حق‌تکثیر در پس‌زمینه در حال پخش باشد نیز تشخیص داده شود.
مرسوم‌ترین پیش‌پردازش ممکن برای استخراج اثر انگشت، شکستن این نمودار بسیار بلند، به پنجره‌هایی (window) با طول ثابت به صورت سر خوردن (sliding window) یا پریدن (hopping window) است که شاید ترجمه خوبی نکرده باشم ولی منظور این است که به فرض اگر ثانیه ۰ تا ۳ را یک پنجره در نظر بگیریم، آیا پنجره بعدی از ثانیه ۳ شروع می‌شود یا از جایی بین ۰ و ۳، که حالت اول hopping window و حالت دوم sliding window است. البته در حالت واقعی، طول پنجره خیلی کوچکتر از ۳ ثانیه و در حد میلی‌ثانیه در نظر گرفته می‌شود. اما اینکه این طول چقدر باشد نیز مشمول همان مصالحه بالا می‌شود.
حالا مساله خیلی کوچکتر می‌شود. در همان مثال قبل که یک صوت یک بار در طیف‌نگاره‌ای که معرفی شد پخش شود و دفعه بعد با تغییر جزئی مثل تغییر کیفیت پخش شود و به پنجره کوتاهی شکسته شود، حالا مساله فقط پیدا کردن شباهت بین دو تصویر است که تقریباً به همدیگر شباهت دارند.
برای این مساله با تکنیک‌های مختلفی، راه حل‌های متفاوتی پیشنهاد شده. به عنوان مقال Shazam از معروف‌ترین سایت‌هایی که همین سرویس را ارائه می‌دهد، پیشنهاد می‌کند که در این تصویر، پر رنگ ترین نقاط را به صورت یک تار عنکبوت به هم وصل کنیم و مختصات آن را نسبت به اندازه پنجره ذخیره نماییم:
که طبیعتاً ذخیره مختصات چند پاره خط به هم پیوسته، فضای ذخیره سازی بسیار کمتری از خود تصویر می‌گیرد. این روش به اعوجاج (distortion) هایی مانند نویز سفید (white noise) مقاوم است. و اینکه چه تعداد از نقاط پر رنگ انتخاب شوند دقیقاً به همان مصالحه بر می‌گردد.
یا همزمان با آن، فیلیپس (Philips) به جای انتخاب نقاط پر رنگ، به دنبال تغییرات در زمان و فرکانس بود و نموداری به این صورت استخراج می‌کرد:
و در نهایت تنها مقادیری را به صورت باینری ذخیره می‌کرد که در آن اختلاف از یک آستانه (threshold) بیشتر باشد. این روش به صورت طبیعی به فرکانس‌های بالاتر بیشتر حساس بود تا فرکانس‌هایی پایین که تغییر کمتری دارند. این روش به نویز‌های انفجاری کمتر حساس بود تا نویز‌های پیوسته.
شیوه‌های دیگری نیز همچون استفاده از هوش مصنوعی برای استخراج بهترین خصوصیات (features) و … مورد استفاده قرار می‌گیرد که بعضی شیوه‌ها مقاوم به نویز انفجاری هستند، بعضی مقاوم به نویز پیوسته، بعضی مقاوم به اعوجاج (distortion)، بعضی مقاوم به کند یا تند شدن سرعت پخش هستند، بعضی قابلیت تشخیص با زمزمه کردن (humming) را دارند و … که بنابر مورد استفاده، باید یکی را انتخاب کرد.
برای ما مقاومت در برابر تغییر‌های شدید مثل کند کردن و ایجاد نویز‌های بلند و طولانی یا هر تغییری که باعث شود کاربر به آن گوش نکند، مهم نبود و طبیعتاً آن Track ها به صورت طبیعی از دور خارج می‌شدند. برای ما صرفاً کپی کردن مهم بود، با تاثیراتی که آپلود مجدد و پردازش مجدد ممکن است بر کیفیت Track بگذارد، قطع کردن بعضی از بخش‌ها و اضافه کردن صداهایی مانند اضافه کردن Watermark صوتی (مانند «ارائه ای از ...» یا «... تقدیم می‌کند»).
روشی که در نهایت مناسب مورد استفاده ما بود، روش دیگری بود که Shazam منتشر کرده بود که لینک آن در بخش منابع قرار داده شده. این روش خیلی مشابه روش اولیست که معرفی شد و در آن قله‌های طیف‌نگاره استخراج می‌شوند، سپس بلندترین آنها یا پررنگ ترین آنها انتخاب شده و خطوطی از آن نقطه به سایر قله‌ها به صورت زیر رسم می‌شود:
در بخش A (مربع بالا، چپ) یک پنجره خاص از یک طیف‌نگاره قابل مشاهده است که قله‌های آن در بخش B (مربع پایین، چپ) استخراج شده که شبیه صور فلکی در آسمان شب است، سپس از میان قله‌ها، بلندترین قله با نام Anchor Point انتخاب شده و همانطور که در بخش C (مربع بالا، راست) قابل مشاهده است، پاره خطی از Anchor Point به تک تک آن قله‌ها رسم می‌شود. به هر کدام از این پاره خط ها، یک اثر انگشت (Fingerprint) گفته می‌شود. در نهایت در بخش D (مربع پایین، راست) می‌توان دید که هر کدام از این پاره خط ها مختصات منحصر به فردی دارند که برای ذخیره آنها به بهینه‌ترین شکل می‌توانند قابل استفاده قرار گیرند. برای ذخیره یک پاره خط، چند راه ساده وجود دارد که ذخیره مختصات x و y نقاط شروع و پایان یکی از آنهاست ولی به دلیل بسیار کوتاه بودن طول پنجره، می‌توان از یکی از اعداد محور x طرف نظر کرد و پاره خط را با مختصات Anchor Point و مقدار y یا فرکانس قله و Δx یا Δt نشان داد.
شیوه ذخیره سازی نیز به این شکل خواهد بود که از کنار هم قرار دادن این ۴ عدد، می‌توان به یک Hash با طول ۳۲ بیت رسید که نشان‌دهنده اثر انگشت است و در یک ستون جدول با نام fingerprint ذخیره می‌شود. در ستون دیگر به نام time_offset زمان شروع پنجره به صورت عدد ۳۲ بیتی ذخیره می‌شود و در ستون آخر با نام file_id، نام یا مسیر یا شناسه یا Hash فایل (مثلاً با یک تابع ساده مانند Jenkins one_at_a_time hash، آن هم به صورت یک عدد ۳۲ بیتی) ذخیره می‌شود. بسته به نوع پایگاه داده (database) این اعداد می‌توانند به صورت علامت دار، بی علامت، ستونی، درختی یا … ذخیره شوند که هر کدام مزیت خودش را دارد. به طور مثال در پایگاه داده Postgresql که از اعداد بدون علامت پشتیبانی نمی‌کند، داده‌ها به این شکل ذخیره می‌شوند:
شیوه دیگری که برای ذخیره اشاره شد، استفاده از درخت است. اگر با عدد fingerprint یک درخت تشکیل شود که برگ‌های آن لیستی از فایل‌ها و زمان پنجره آنها در کنار هم به صورت یک عدد ۶۴ بیتی باشد، زمان جستجو و پیدا کردن Track مشابه را به شدت کاهش می‌دهد اما زمان وارد کردن داده‌ها را کند تر می‌کند.
در شیوه‌ای مشابه می‌توان از پایگاه داده‌های کلید و مقداری (key-value) مانند redis استفاده کرد و مقدار fingerprint را به عنوان کلید و لیستی از فایل و زمان شروع پنجره ها را به عنوان مقدار در آن قرار داد. این پایگاه داده حتی می‌تواند یک File System باشد و نام هر فایل، همان اثر انگشت و مقدار داخل آن، همان لیست قبل به صورتی که هر خط شامل یک فایل و زمان شروع پنجره باشد.
بعد از ذخیره اثر انگشت‌های Track ها، حالا باید روشی یافت تا یک Track دلخواه را به سیستم داد و Track های مشابه را استخراج کرد. شیوه‌های تطابق صوتی دو Track نیز فراوان هستند ولی انتخاب آن کاملاً وابسته به شیوه اثر انگشت گیری است. برای شیوه اثر انگشت گیری مطرح شده، نحوه تطابق صوتی به این صورت است که به همان شیوه قبل، فایل صوتی به پنجره‌هایی با طول ثابت تقسیم شده، اثر انگشت‌های آن پنجره که در حقیقت Hash هایی از مختصات چند پاره خط هستند استخراج می‌شوند. این Hash ها در پایگاه داده جستجو می‌شوند و متناظر با آنها، لیستی از فایل‌ها به همراه زمان شروع پنجره آنها بدست می‌آید. به این ترتیب برای هر پنجره از فایل مورد نظر، لیستی از فایل و زمان شروع‌های دیگر بدست می‌آید که می‌توان تعداد تکرار آنها را برای تمام اثر انگشت‌های پنجره مورد نظر بدست آورد.
به عنوان مثال اگر فایل های audio1 و audio2 و … تا audio10 را قبلاً در پایگاه داده ذخیره کرده باشیم و فایل query را مورد بررسی قرار دهیم، برای دو پنجره اول ممکن است اطلاعاتی شبیه به این بدست بیاید:
برای پنجره شماره ۱ از فایل query:
تعداد ۴ اثر انگشت از پنجره شماره ۶ فایل audio1
تعداد ۱۲ اثر انگشت از پنجره شماره ۴ فایل audio2
تعداد ۲ اثر انگشت از پنجره شماره ۸ فایل audio3
تعداد ۲۰ اثر انگشت از پنجره شماره ۹ فایل audio4
برای پنجره شماره ۲ فایل query:
تعداد ۵ اثر انگشت از پنجره شماره ۷ فایل audio1
تعداد ۱۴ اثر انگشت از پنجره شماره ۵ فایل audio2
تعداد ۱۹ اثر انگشت از پنجره شماره ۱۰ فایل audio4
در این مرحله، برای حذف نتایج مثبت کاذب (False Positive)، آنهایی که تعداد اثر انگشت منطبق شده شان کمتر از یک عدد از پیش تعریف شده در تنظیمات (مثلاً کمتر از ۱۰) باشد را حذف می‌کنیم. بنابراین audio1 و audio3 از نتایج حذف می‌شوند. بعد از این مرحله، خود اثر انگشت‌ها بی‌معنی می‌شوند و صرفاً پنجره‌های منطبق شده، برای پیدا کردن تشابه استفاده می‌شوند.
تا اینجا پنجره‌هایی که بین دو فایل مشترک بودند را پیدا کردیم و می‌توان در همین مرحله با درصد پنجره‌های تطابق یافته نسبت به کل پنجره‌ها، درصد تشابه دو فایل را بدست آورد. اما می‌توان کار را یک مرحله بیشتر پیش برد و توالیهای مشترک بین Track ها را پیدا کرد تا دقیقاً مشخص باشد کدام بخش از یک موسیقی دارای حق‌تکثیر، در کدام بازه از Track دیگر استفاده شده تا بتوان گزارش دقیق‌تر داد یا به صورت خودکار، آن بخش از Track را بی‌صدا (mute) کرد.
به نظر می‌رسد که مساله حالا پیدا کردن بلندترین زیردنباله مشترک (LCS) باشد، ولی یک نکته مهم در داده‌های بالا هست که شاید کار را راحت تر کند و از نظر کارایی، بهتر عمل کند؛ با توجه به لیست بالا، طبیعی است که اگر پنجره شماره ۱ فایل query با پنجره ۴ فایل audio1 منطبق شده باشد، در صورتی فایل audio1 همچنان در این توالی قرار دارد که پنجره شماره ۲ فایل query با پنجره ۵ فایل audio1 تطابق داشته باشد. یا به عبارت دیگر، در پنجره شماره ۱ فایل query، پنجره ای از فایل audio1 پیدا شده که با آن اندازه ۳ پنجره فاصله دارد (پنجره ۴ منهای پنجره ۱) و در پنجره شماره ۲ فایل query نیز پنجره ای از فایل audio1 پیدا شده که با آن اندازه ۳ پنجره فاصله دارد (پنجره ۵ منهای پنجره ۱). پس می‌توان از اختلاف پنجره‌های دو فایل برای ترکیب کردن پنجره‌ها استفاده کرد تا به توالی‌هایی از دو فایل رسید که با یکدیگر منطبق باشند.
اگر از شماره فایل‌ها به همراه اختلاف پنجره‌های دو فایل فاکتور بگیریم، به یک دیکشنری می‌رسید که مقادیر آن، صرفاً لیستی از شماره پنجره‌هاست. حال می‌توان در هر لیست، پنجره‌هایی که در حداکثر فاصله مشخصی از هم (مقدار آن به صورت پیشفرض در تنظیمات داده می‌شود) هستند را با همدیگر ترکیب کرد و به زیردنباله‌هایی رسید. سپس این دیکشنری را دوباره به لیستی از شماره Track و اختلاف پنجره‌های دو فایل و زیردنباله ها به صورت flat تبدیل کرد و دوباره از شماره Track ها فاکتور گرفت و عملیات قبل را دوباره انجام داد تا بتوان مطمئن شد که تمام توالیهای فایل که حداکثر فاصله مشخصی دارد (این مقدار هم به صورت پیشفرض در تنظیمات داده می‌شود و با قبلی یکسان نیست)، با همدیگر ترکیب شده و بلندترین توالی مشترک را بدست آورده باشند. با ضرب کردن طول دنباله در طول زمانی ثابت پنجره، نتیجه می‌شود لیستی از بلندترین توالیهای فایل‌های داخل پایگاه داده با فایل query.
در صورت نیاز به بدست آوردن درصد تشابه دو فایل در این مرحله می‌توان مجموع نسبت توالیهای مشترک دو فایل به طول زمانِ طولانی‌ترین فایل از این دو را حساب کرد و به صورت درصد نمایش داد.
برای پیاده‌سازی، دو راه پیش رو بود: اختراع دوباره چرخ و استفاده از یک چرخ مناسب و ایجاد تغییرات در آن. در واقعیت تقریباً همیشه گزینه اختراع دوباره چرخ منتفی است، چون هیچ شرکتی بودجه، زمان و تمایل به این کار ندارد، اما همین پست هم خود، اختراع دوباره چرخ است!
به هر حال، از بین پیاده‌سازی‌های موجود، که تعداد آن نیز کم نیست، Olaf توجه ما را جلب کرد. داستان آن به پدری بر می‌گردد که می‌خواست برای دخترش لباسی طراحی کند که هرگاه آهنگ انیمیشن Frozen پخش شد، لباس شروع به چشمک زدن بکند و تمام این اتفاقات به صورت نهفته (embedded) در یک میکروکنترلر با کمترین منابع ممکن و به بهینه‌ترین شکل ممکن پیاده شود.
این پروژه تقریباً همان مسیری را در پیش گرفته که در بالا توضیح داده شد، با اندکی تفاوت و اندکی اشکالات. به عنوان نمونه، برای ذخیره‌سازی از دیتابیس LMDB استفاده می‌کند که همان ساختار درختی ای است که توضیح داده شد. پیاده سازی آن اشکالاتی نیز دارد، مثلاً Track هایی یافتیم که طول آنها چند دقیقه بود، ولی شباهتی که بین آنها پیدا می‌کرد، چند هزار ساعت بود!
اما حالا ما برای شروع یک کد به زبان C داشتیم و چون C زبان مرسوم شرکت نیست، تصمیم گرفتیم ابتدا یک wrapper روی آن بنویسیم و سپس تکه تکه بخش های مختلف آن را به زبان Go بازنویسی (port) کنیم. همچنین تصمیم گرفته شد که از LMDB استفاده نکنیم، زیرا به دلیلی که قبلاً توضیح داده شد، رفته رفته سرعت درج اطلاعات در آن کندتر و کندتر می‌شود.
تمام ایده‌هایی که در بالا توضیح داده شد و تمام پایگاه داده‌ها در آن گنجانده شد و نتیجه این شد:
بهینه بودن کد برای ما اهمیت بسیار بالایی داشت، زیرا فقط با یک آهنگ Frozen سر و کار نداشتیم و باید جوابگوی روزانه چند صد Track ای که به سیستم اضافه می‌شد، می‌بود. در هر مرحله نیز تست‌هایی انجام شد که مطمئن باشیم بازنویسی درست انجام شده و نتایج ما با Olaf یکی است و در نهایت از آن نیز بهتر است.
این پروژه، دو فایل باینری تولید می‌کند که یکی عیناً مانند Olaf عمل می‌کند و دیگری از یک صف، Track هایی که باید پردازش شوند و به پایگاه داده اضافه شوند را می‌گیرد، پردازش می‌کند، Track های تکراری یا تقریباً تکراری را پیدا می‌کند و در یک جدول در پایگاه داده ذخیره می‌کند و سپس اثر انگشت‌های فایل پردازش شده را به پایگاه داده می‌فزاید.
با استفاده از این کد، تا به حال حدود یک میلیون عدد از Track ها بررسی شدند که مشخص شد حدود ۸.۳۰٪ از آنها کپی بودند. همچنین اطلاعات دقیقی از این پردازش بدست آمد که تمام اهداف ذکر شده در ابتدای پست را ممکن ساخت.
How does Audio Fingerprinting work
Shazam : An Industrial Strength Audio Search Algorithm
An industrial-strength audio search algorithm (2003)
Seeing Through Sound: Acoustic Fingerprinting
OLAF: Overly Lightweight Acoustic Fingerprinting
Olaf - Acoustic fingerprinting on the ESP32 and in the Browser
Panako: a scalable acoustic fingerprinting system handling time-scale and pitch modification
