-
Notifications
You must be signed in to change notification settings - Fork 168
conference talk
(дякую за організацію і запрошення)
окей, перед тим як почнемо - хто знайомий з Шазамом?
В кафешці заграла майже забута пісня. Ви її колись-далеко-десь чули. Ця пісня викликала якісь згадки у вас. Ви дуже сильно сильно хочете її знову послухати, але назва пісні вилетіла у вас з голови. Як бути?
На щастя в нашому фантастичному світі є відповідь на таке питання - і називається вона Шазам.
Про шо будемо сьогодні говорити:
- СИГНАЛ - чому наші вуха можуть його чути, і як навчити компютер їх чути
- ПЕРЕТВОРЕННЯ ФУРЄ - як навчини компютер розуміти цей сигнал
- СПЕКТРОГРАМИ - аля теплові карти сигналу
- як взяти (відбиток пальця) в АУДІО, але так шоб він був реально УНІКАЛЬНИМ для кожного аудіо (мінімізувати кількість колізій)
- ЯК оптимізовано ЗБЕРІГАТИ, і шо саме зберігати
- підсумуємо все до купи, і побачимо ЯК ПРАЦЮЄ ШАЗАМ?
- ДЕМО
Не будемо говорити про:
-
ЗВУК
- механічні коливання, які розповсюджуються в твердих, рідких і гозоподібних середовищах
- МАТЕМАТИКУ
-
ДИСКРЕТИЗАЦІЮ
- перетворення аналогово звуку в цифровий
- нехай це поки залишиться таємною безтілесною субстанцією
- типу РЯДИ ФУРЄ
- MATLAB
Останні Х місяці я працюю на аутсорс компанію Х. Я викладаю і драйваю ФЕ поток.
(пару слів про CURSOR, UASC, стартапи)
зовсім чуть чуть про те, як виглядає світ "sound recognition".
- (сказати про шазам 1999)
- (сказати про схожі аппки)
Патенти. Ми, фактично, розберемо один із них який не розповсюджується на країни СНГ.
(розказати про shazam-java, якого адвокати хотіли засудити).
Почнемо ми з того (точкою відправлення в світ Шазаму) ми подивимося на бумагу. Складається з 6 сторінок.
Написана в 1999 (оновлена в 2003) автором Shazam.
В загальному вона пояснює як можна зняти відбиток з аудіо-сигналe, шоб його співставляти з іншими і потім ідентифікувати.
Написана тоді коли у нас не було ше смарфонів і айфонів. У нас було шось типу нокії 3310.
Ми перейдем до першого параграфу.
flexible audio search engine
- Google = text search - дав текст, отримав текст
- Shazam = дав audio, отримав метадані або шось звязане з аудіо
noise and distortion resistant
- Google = spelling помилка - постарається вас виправити
- Shazam = алгоритм Шазаму скіпне шум
massively scalable
- db of more than 11 mil songs
- Shazam менеждить це дуже добре
- спочатку розуміли шо будуть мати справу з Big Data,
- і з самого початку вони заклали в архітектурі потрібні принципи
combinatorially
- отут з першого погляду взагалі неясно шо вони хотіли цим сказали
- про це я і буду сьогодні говорити
На сьогоднішній день існує дуже багато методів розпізнавання звуку.
В загальному вигляді більшість методів складаються із декількох кроків:
- алгоритм зняття сигнатури (fingerprints) сигналу. Максимально компактним, але при цьому найбільш точно описувати аудіо.
- алгоритм пошуку в базі даних
- алгоритм відсікання помилкових спрацьовувань
Важлива ефективність алгоритма, і наскільки він може працювати з спотвореними даними.
Шоб зрозуміти шо це таке, уявіть собі ноту на фортепіано.
При натисканні клавіші фортепіано молоток вдаряє по струні, яка вібрує з певною частотою (нота Ля — 440 раз в секунду).
Поки струна вібрує, навколо неї рухаються молекули повітря взад і вперед, створюючи хвилю з молекул, яку ми називаємо звуком.
Якби ви могли спостерігати за рухом повітря, то побачили б гладку, хвилясту, нескінченно повторювану криву, яка називається синусоїдою.
АЛЕ у прикладі з клавішею фортепіано насправді виникає більше однієї синусоїди. Нота приблизно дорівнює синусоїді, але за допомогою камертона можна отримати звук, який складається з однієї синусоїди).
Щоб отримати акорд, тепер натисніть на три клавіші разом.
Отримана звукова хвиля вийде не такий акуратною - вона буде більш безладна. Але в цій кривій звуковоъ хвилі прихований простий малюнок. Бо акорд ми отримали, натиснувши всього на три клавіші, так що ця звукова хвиля складається з трьох нот (або синусоид).
Це всього лише сума трьох різних нот.
Майже кожен аудіо любитель, навіть НЕ математик чув про велике і ужасне перетворення Фур'є.
Його знайшов і зрозумів француз в 18-му столітті (жан батист жозеф фурье). Це, доречі, той самий дядько хто відкрив парниковий еффект.
Те шо він придумав, це найбільш широко використовуване математичне відкриття.
- пульс биття сердця
- радіо-астрономія
- його модифікації використовуються в компресії MP3 і JPEG
- ретнген і МРТ
- розпізнавання голосу
- і купа іншого
Фур'є здогадався, що це не просто особлива властивість музичних акордів, воно може бути застосовано в до будь-якої періодичної хвилі
- квадратної, круглої, хвилястою, трикутної
Перетворення Фур'є схоже на математичну призму:
- ви подаєте хвилю
- а воно показує її складові частини
- тобто ноти (або синусоїди), які при з'єднанні відтворять хвилю
- інтенсивность сонячного променя, яке входить в призму, постійно міняється в часі
Не будемо заглиблюватися в математику, в складності інтегральних числення, не будемо докопуватися до істини чому і як саме воно працює, бо це глибоко математична штука.
Ви напевно користуєтеся ідеєю Фур'є кожен день:
- коли слухаєте MP3
- дивитесь картинки в Інтернеті
- задаєте питання до Siri
- або просто ловите радіостанцію
Трюк Фур'є відбувається кожен раз коли ми чуємо звук.
Людське вухо автоматично виконує обчислення. Щоб навчити копютер це робити - для цього виконується перетворення Фурє.
Червона квадратна хвиля конвертується в набір нот (сині синусоїдальні хвилі). Сині хвилі – це математичні інгредієнти червоною хвилі.
З цієї ж аналогією перетворення Фур'є є рецептом, який точно вкаже, скільки і якої ноти потрібно змішати разом, щоб відновити ісходнік (сорс) хвилі.
Оці вертикальні сині лінії в анімації – це графік, який візуально представляє кількість кожної ноти.
Два чувака
- Matthew Henderson
- LucasVB (twitter)
Пояснюють трюк Фуре, використовуючи круги (кола) замість синусоїд. Круги різних розмірів, які крутяться один навколо іншого.
Уявіть, що ви говорите зі своїм другом по телефону і хочете, щоб він намалював цю квадратну хвилю.
Можна використовувати довгий спосіб і зачитати довгий список цифр, які показують висоту хвилі в кожен момент часу. Маючи ці числа, ваш друг сможет відтворити початкову хвилю.
Так працюють старі аудіо формати, типу WAV. Він зберігає інформацію в вигляді залежності амплітуди від часу.
Але якшо ваш друг знає шось про трюк Фурье, можна зробити все простіше:
- ви можете просто назвати декілька чисел — розміри кругів
- ці круги можна можна використати шоб відтворити початкову хвилю.
І це не якись складний математичний фокус. Це те, шо використовує в себе MP3. Як результат - розмір mp3-шок менший за wav-файли.
MP3 разбивает песню на короткие сегменты. В каждом сегменте преобразование Фурье разбивает аудио волну на составляющие ноты, которые хранятся вместо исходной волны. Преобразование Фурье также говорит нам, сколько и какой ноты используется в песне, чтобы знать, какие ноты важны. Очень высокие ноты не так важны (наши уши едва слышат их), поэтому МР3 выбрасывает их, добиваясь еще большего сжатия данных.
Чому меломанам не подобається МР3 — бо це не lossless формат аудіо, і вони кажуть, що можуть почути різницю.
Shazam якраз так зберігає треки.
Він розбиває аудіо-інпут на куски, потім робить петерворення Фурье, щоб визначити ноти, з яких складається кожен шматок.
Розпізнавання голосу використовує ту ж саму ідею, шоб порівняти ноти із голоса із списком відомих слів.
Microsoft Paint зберігав в BMP, який представляв собою довгий список чисел, які кодують колір кожного пікселя. Зявився JPEG – это MP3 зображень.
Чтобы создать JPEG, надо разделить изображение на мелкие квадраты 8 на 8 пикселей. Чтобы воссоздать изображение, для каждой части нужно применить ту же идею круга. Так же, как МР3 отбрасывает очень высокие ноты, JPEG отбрасывает очень маленькие круги. В результате мы получаем огромное уменьшение размера файла при небольшой потере качества. И благодаря которому у нас появились гифки с котиками.
LucasVB запитав різни наукових дядьків в твіттер, як вони ше використовують Фурє:
- для передбачення землетрусів
- для визначення складових частин дуже далеких галактик
- для пошуку нових фізичних процесів
- в радаре, используемом ГИББД
- Радар отправляет порцию колебаний известной частоты, а затем принимает отражённый сигнал
- эффекту Доплера
- обратно возвращается смесь сигналов с различным значением смещения несущей частоты
- частота отражённого сигнала меняется пропорционально скорости движущегося объекта
- Зная разность частот отправленного и принятого сигнала, радар может очень точно вычислить скорость
- если по трассе едут 5 автомобилей с разной скоростью, радар выдаст 5 замеренных скоростей, заодно указав максимальную
Перетворення Фурье навіть використовувалось для визначення фальшивих картин Джексона Поллока через розпізнавання хімічних речовин у фарбі.
Summary - принцип перетворення Фурье похожий на декомпіляцію. Тільки хвиля не «розбивається на ісходнікі», а «розкладується по синусам».
Я обіцяв шо не буде математики, тому скажу тільки що існує Куча модифікацій перетворення Фурье. Коли Фурє - це залежність амплітуди від частоти, так є модицікації залежності амлітуди и початкової фази сигналу, і тд.
Ще одна модифікація в математиці цього перетворення, яка позволяє значно пришвидшити цей процес.
В себе в демо, я використав якраз Швидше Перетворення Фурє.
Придумали чуваки з IBM & Bell, в 1965 году.
- метод БПФ предложен в 1805 году Гауссом и переоткрыт в 1965 году
В методі швидкого перетворення Фурье крива ділиться на велике число рівномірно розподілених значень (семплів).
Ще одна модифікація перетворення Фурє.
Придумали в MIT (Массачусетський технологічний інститут) в 2012.
- В десятки разів прискорює швидке перетворення Фурє.
- В десятки тисяч разів щвидше за БПФ.
Ну і ше одна модифікація, яка є ше швидкою.
Audio fingerprint (до якого ми рухаємось) він базується на spectogram (called time-frequency graph).
Спектрограма - картинка, показує залежність плотності мощності сигналу від часу.
Спектрограма генерується так:
- в звуковом сигналі через рівні проміжки часу вирізаються маленькі «вікна»
- для кожного такого вікно робиться перетворення Фуре (АЧХ)
- тобто у вас є для кожного моменту часу своя АЧХ
Я думаю можна slide-next.
Ось це і є залежність між «частота-время».
- На горизонтальной осі - час.
- Но вертикальній осі — частота.
Треба slide-back.
Ще на третього вимірі показується амплітуда
- на конкретній частоті
- в конкретний момент часу
- яка показує інтенсивність або кольором кожного точки зображення
Це Spectrogram якогось шматка аудіо треку. Ми можемо побачити залежності типу нот тут.
Але, проблема в тому як зберігати ці дані.
Шазар вміє брати цей великий поток данних, і перетворити їх в набагато менше данних.
Один із способів це зробити - acoustic fingerprints. Це і є ключевим елементом того як працює Шазам.
стеганография
В монохромному форматі.
- на 4й секунді - пік 1300 Hz
- на 7й секунді - пік 1700 Hz
- etc
Ближче до acoustic fingerprints який робить Шазаму. Він робить це по дуже простому шляху.
Тут зявляється нове зпитання - шо саме нам зберігати? Оскільки, Fingerprint — має бути компактним, але і стійким до спотворень.
Загальний процес розпізнавання полягає в створенні fingerprint вхідного аудіо-сигналу і пошуку по базі еталонних зразків, ну і потім може видати релевантну інфу по найдемо треку (назва, оффсет).
Фішка Шазаму в cons-te-ll-ation map (сузіря).
Можна собі представити шо кожна крапочка на цій мапі - це окрема нота. Кожна з цих точок (нот) має позицію по часу і частоту.
Це доволі круто, бо маючи реально величезний поток даних ми змогли відкинути дуже багато не критично важливої інфи.
І в результаті вийшло шось типу унікального представлення аудіо.
Ні одне інше аудіо не буде мати 100% співпадіння з цим. Ні один шматок вашої музики не буде 1-в-1 схожим із цим.
Це фактично перший крого того шо робить Шазам. Але це ше не все.
Тут у нас зявляється проблема - всі вони залежать від часу. У випадко якшо запис йде не з першої секунди - фейл.
Тобто, такий fingerprint цілого файлу ніяк нам не допоможе знайти співпадіння якогось сегменту в аудіо.
Це дуже важливо, бо Шазам дозволяє шукати в любому місці в треку.
В бумазі в розділі "Combinatorial Hash Generation", описано: зберігає не координати пікових точок, а звязки між ними.
Якщо представити що одна точка це нота, то хеш - в представленні Шазаму - це одна пара ноут.
Ми можемо описати одну пару нот (один сегмент):
- як початкова-кінцева нота (їх частоти)
- і різниця в час
talk
talk
- чим більше співпадінь таких хешів - тим ймовірніше
- провіряємо також порядок