HOLO — The Music Amalgamation System

    HOLO — приставка от греческого ὅλος, «весь».
    Введение

    Не без волнения рад представить вашему вниманию свою разработку, позволяющую объединять музыкальную библиотеку в единое целое с целью поиска «похожей» музыки.
    Ещё несколько лет назад, на пике самостоятельного изучения MATLAB, мне захотелось создать программу, которая позволяла бы по заданному образцу музыки находить другие композиции «в том же духе». Куча уважительных причин заставляли откладывать реализацию всё дальше и дальше, но в какой-то момент дело сдвинулось с мёртвой точки. В результате, слегка изменив основу для разработки, первая версия программы была сделана.

    Постановка задачи

    Итак, постановка задачи выглядит следующим образом:
    1. Есть сравнительно большая (>10 тыс. файлов) музыкальная коллекция на жёстком диске, целиком которую использовать и каталогизировать стало затруднительно, из-за чего многие композиции месяцами и годами ни разу не попадают в плейлист.
    2. Необходимо провести оценку численных характеристик композиций, не используя никакой информации кроме формы звуковой волны, содержащейся в файле (никаких имён файлов, альбомов, id3-тегов и тому подобное в расчёт не берётся).
    3. Подать анализатору на вход одну или несколько композиций в качестве образцов.
    4. Вывести список композиций, не совпадающих со списком образцов и отсортированных в порядке возрастания их «расстояния» от образцов.

    Платформой для разработки стал C#, как наиболее простой лично для меня язык, достаточно быстрый и имеющий хорошую среду разработки. Беглый поиск по Codeplex и подобным сайтам позволил избежать изобретения некоторых велосипедов, в частности используются следующие библиотеки:
    1. NAudio – для считывания аудиофайлов.
    2. Meta.Numerics – для FFT-преобразования.
    3. SQLite + SQLite netFX wrapper для хранения и обработки данных.
    4. Также на стадии исследования подключена библиотека ALGLIB в версии для .NET.

    Архитектурно программа состоит из двух подсистем – формирование базы данных о музыкальной коллекции и система поиска по базе данных.
    Теория

    Формирование базы данных реализовано следующим образом:
    Анализируемый файл представляется в виде вектора из семплов, из которого извлекается N снимков (snap) длиной L семплов, каждый из которых приводится в АЧХ (fft-snap) при помощи FFT-преобразования. Это преобразование, по сути, превращает временной ряд в набор амплитуд разных частот, из которых состоит временной ряд. Затем fft-snap пропорционально сжимается в K раз (downscale ratio), чтобы уменьшить количество анализируемых в дальнейшем частот.
    Далее каждая частота получившегося набора снимков рассматривается по-отдельности – рассчитываются статистические характеристики, такие как среднее значение (mean), медиана (median), стандартное отклонение (stdev), скос (skewness) и крутизна (kurtosis). В результате, для каждой композиции имеем набор из L/2K частот (FFT получается практически симметричным относительно середины), для каждой из которых рассчитаны 5 статистик. В базу данных кладётся имя файла, путь к нему на диске и 5L/2K вещественных чисел, каждое из которых помечено именем статистики, которое оно представляет.
    Например, мы анализируем файл, сделав 40 снимков длиной в 64000 семплов, сжатых в 1000 раз. В итоге имеем вектор из 5*(64000/1000)/2 = 160 чисел для каждой композиции.
    На этом основной этап формирования БД для анализа считаем завершённым. Вспомогательными шагами являются:
    1. Построение индекса по таблице статистики.
    2. Расчёт габаритных значений для каждой статистики (максимум, минимум, среднее и коридор – разница между максимумом и минимумом).

    Теперь можно приступать к анализу. Простейший способ оценить близость двух точек в 160-мерном пространстве – посчитать евклидово расстояние между ними (сумма квадратов попарных разностей соответствующих статистик, квадратный корень не извлекаем — он удлиняет вычисления, но на результат сортировки не влияет). Казалось бы – бери и считай, но разные частоты в АЧХ композиции имеют разные разбросы и расчёт расстояния «в лоб» будет давать искажённое расстояние, с сильным акцентом на низкие частоты. Для того чтобы компенсировать нежелательный эффект, мы поделим квадрат разности между значениями на квадрат среднего значения амплитуды данной частоты. Таким образом, исходно анизотропное пространство характеристик распределения частот, в котором мы вычисляем расстояние, становится значительно более изотропным, то есть однородным.
    Теоретически, можно провести кластерный анализ, объединяющий композиции по степени их близости, но пока было решено отказаться от применения этого метода, так как в его основе также лежит расчет расстояния между точками в пространстве (с выбором разных метрик), но алгоритм оказывается более сложным и не очень полезным в задаче сортировки композиций по возрастанию расстояния.

    Практика

    Пожалуй, теории пока достаточно, расскажу о практических результатах на основе моей коллекции музыки. Количество треков 30277, жанры самые разные – классическая музыка, рок, хард-рок, эмбиент, драм-н-бейс, хаус, техно, этника, весь спектр металла от лёгкого дума до самого ядерного и быстрого.
    Анализ всей моей коллекции занял два с половиной дня, база данных без постобработки занимает 180 мегабайт, вместе с индексами — 460.
    Интерфейс программы в части поиска заключается в динамическом формировании SQL-запроса, в котором реализован алгоритм расчёта евклидова расстояния для нормированных статистик по каждой частоте.
    Имеется возможность указать как одну композицию в качестве образца, так и несколько. Вообще, возможность поиска песен, близких сразу к нескольким образцам, сильно увеличивает точность поиска, так как одна композиция может иметь паразитные вариации по статистикам, возникающие по разным причинам, но нивелируемые благодаря тому, что несколько образцов по-сути образуют центроид в многомерном пространстве, паразитные вариации которого сильно уменьшены. Главное при определении нескольких образцов — быть уверенным в том, что между образцами действительно имеется явная общность (например, композиции с одного альбома или в одном узком жанре и т.д.). Если образцы будут сильно отличающимися между собой, то выдача близких композиций будет нерелевантной.
    Запрос при одном образце выполняется в среднем около минуты, при увеличении количества образцов время увеличивается пропорционально.

    Образец SQL выглядит следующим образом:
    select b.id, sum(((a.statvalue - b.statvalue)*(a.statvalue - b.statvalue))/(c1.value*c1.value)) as distance, 
    10000*max((a.statvalue - b.statvalue)*(a.statvalue - b.statvalue)/(c2.value*c2.value)) as maxdiff, 
    10000*avg((a.statvalue - b.statvalue)*(a.statvalue - b.statvalue)/(c2.value*c2.value)) as meandiff 
    from stats a, stats b, feature c1, feature c2 
    where 
    a.id in (631, 1919) and b.id not in (631, 1919) and 
    a.statname = c1.statname and c1.feature = 'mean' and 
    a.statname = c2.statname and c2.feature = 'max_min' and 
    a.statname = b.statname and c1.statname = c2.statname and 
    a.statvalue <= b.statvalue + 75*c2.value/100 and a.statvalue >= b.statvalue - 75*c2.value/100 and 
    a.statname in ('b_median_FFT1_01', 'b_median_FFT1_02', 'b_median_FFT1_03', 'b_median_FFT1_04', 'b_median_FFT1_05', 'b_median_FFT1_06', 'b_median_FFT1_07', 'b_median_FFT1_08', 'b_median_FFT1_09', 'b_median_FFT1_10', 'b_median_FFT1_11', 'b_stdev_FFT1_01',  'b_stdev_FFT1_02',  'b_stdev_FFT1_03',  'b_stdev_FFT1_04',  'b_stdev_FFT1_05',  'b_stdev_FFT1_06', 'b_stdev_FFT1_07', 'b_stdev_FFT1_08', 'b_stdev_FFT1_09', 'b_stdev_FFT1_10', 'b_stdev_FFT1_11',
    'b_skewn_FFT1_01',  'b_skewn_FFT1_02',  'b_skewn_FFT1_03',  'b_skewn_FFT1_04',  'b_skewn_FFT1_05',  'b_skewn_FFT1_06', 'b_skewn_FFT1_07', 'b_skewn_FFT1_08', 'b_skewn_FFT1_09', 'b_skewn_FFT1_10', 'b_skewn_FFT1_11', 'b_kurto_FFT1_01',  'b_kurto_FFT1_02',  'b_kurto_FFT1_03',  'b_kurto_FFT1_04',  'b_kurto_FFT1_05',  'b_kurto_FFT1_06', 'b_kurto_FFT1_07', 'b_kurto_FFT1_08', 'b_kurto_FFT1_09', 'b_kurto_FFT1_10', 'b_kurto_FFT1_11') 
    group by b.id 
    having maxdiff <= 100 and meandiff <= 64 
    order by distance limit 30;
    


    В качестве примера, приведу результат работы запроса из трёх образцов песен, взятых с альбома “Songs of Darkness, Words of Light” группы My Dying Bride:
    Эти композиции являются хорошим образцом жанра death-doom metal.

    Посмотрим, выдача размером в 30 композиций выглядит следующим образом:
    1. F.U.B.A.R. — Crawling Релевантность, пожалуй, только по фактуре гитарного звука.
    2. The Soundbyte — The Dark Много электроники, но по атмосфере совпадение отличное.
    3. AHAB — Ahabs Oath В точку!
    4. Gorement — Into Shadows Чуть более экстремально чем образец, тем не менее очень близко.
    5. Tombs — Marina Абстрактный сладж-дум, по фактуре похож.
    6. Esoteric — Allegiance В точку!
    7. Autechre — Eutow Очень неожиданный вариант, но если послушать, то можно почувствовать параллели по фактуре звука.
    8. Entombed — Retaliation Не в точку, но очень близко.
    9. Quake Mission Pack 1 — Scourge of Armagon — 04-music-track-4.mp3 Смешной вариант, но в целом релевантность оказалась высокая.
    10. Nile — Divine Intent Первая часть песни в точку, дальше звучит более интенсивно, чем образцы.
    11. Янтарные Слёзы — За Край Небес В точку!
    12. NEUROSIS — Times of grace Слегка другой жанр, но релевантность высокая.
    13. Young Widows — In And Out Of Youth Высокая релевантность.
    14. Empyrium — Autumn Grey Views Тоже дум-метал.
    15. Dark Tranquillity — Hours Passed In Exile Более экстремально, но релевантность хорошая.
    16. Shape of Despair – Quiet These Paintings Are В точку!
    17. Rosetta — A Determinism of Morality Высокая релевантность.
    18. Solstafir – Ghosts of Light Очень высокая релевантность.
    19. Led Zeppelin — Ten Years Gone Неожиданный вариант, но в целом тоже принимается.
    20. Typhus — ***CENSORED*** Релевантность высокая, название трека зацензурировал как неприличное для сайта.
    21. Voivod — Divine Sun Релевантность приемлемая.
    22. Cradle of Filth — Malice Through The Looking Glass Очень хороший, хотя и неожиданный вариант.
    23. Suffocation — Redemption Релевантность портится из-за большей экстремальности.
    24. Nihilist –Abnormally Deceased Совпадение по фактуре гитарного звука.
    25. Reverend Bizarre – The Gate of Nanna В точку!
    26. Goresleeps — Avalon Dreams (The Voice From Legend) В точку!

    Плюс ещё 3 нерелевантных трека и 1 дубликат того что уже есть в списке. По-моему, уже достаточно приемлемо. Во всяком случае, я бы не отвергал такой плейлист, если бы захотелось послушать чего-то «в духе MDB».


    Мог бы привести другие примеры, но в целом хочу сказать, что пока наиболее простым по идентификации жанром для программы является эмбиент (Aidan Baker, Tetsu Inoue, Lustmord и другие, тысячи их).

    Недостатки

    Конечно, они тоже есть, прежде всего из-за того что алгоритм сравнения далёк от совершенства.
    1. Программа не учитывает среднюю громкость. Поэтому, кстати, в выдаче могут вылезти песни 80-х, в то время как образец из 2000-х, когда война громкостей уже была на исходе.
    2. По моей БД регулярно появляются заведомо нерелевантные композиции из ограниченного списка, наличие которых в результатах я пока объяснить не могу. Для таких случаев сделан список исключений.
    3. По-моему мнению, главный фейл – программа практически никогда не выдаёт песни с того же альбома, если в качестве образца уже взято несколько. В редких случаях одна-две, не более того.
    4. Похожий недостаток – вывести все песни, скажем, Земфиры, задав в качестве образца две-три её же песни. Голос, конечно, отличительная особенность, но фоновые инструменты, звучащие по-разному в разных композициях нарушат условия для благоприятного поиска. Возможно, если повысить разрешение анализа по частотам и добавить количество образцов по каждой песне, то на что-то можно надеяться, но тогда скорость работы может сильно упасть.
    5. Центральные моменты N-го порядка в целом неплохо характеризуют композиции, но две из них (skewness & kurtosis) трудно привязать к слышимым характеристикам звука. Может быть, это и не настолько плохо, но хотелось бы иметь более понимаемые метрики.
    6. Скорость работы: в среднем по минуте ожидания на каждый трек в списке образцов – в целом терпимо, но очень хотелось бы быстрее. Текущая архитектура запроса с сортировкой по возрастанию неизбежно заставляет SQLite делать полный прогон всех композиций, не смотря на наличие индексов, отключение же сортировки может многократно ускорить работу. Кстати, на случай работы без сортировки предусмотрены дополнительные методы отбора вариантов.


    Исходники выложил на Github. (Кое-как удалось сделать пуш репозитория, первый раз в жизни, эхехех. Желающие помочь с выкладкой — прошу в ЛС, нужна небольшая консультация)
    Для нежелающих возиться с гитхабом, выложил бинарники на гугл.драйв. Нужно нажать Ctrl+S чтобы сохранить архив себе.

    По первым пользователям стало понятно что не у всех стоит ACM-кодек MP3, из-за этого файлы могут не обрабатываться. Не уверен, но скорее всего должна помочь установка K-Lite Codec Pack, например.

    Прошу сильно строго не судить, делается всё на энтузиазме. Программирование на C# не является для меня основным профессиональным занятием.
    Программа умеет сохранять и открывать плейлист, по двойному клику из списка образцов и списка результатов треки также можно открывать на прослушивание.

    Если найдутся желающие помочь с оптимизацией SQL-запроса или формулированию дополнительных метрик кроме вышеописанных — пишите личные сообщения, буду рад сотрудничеству.
    Если возникнут какие-либо ошибки при попытке запуска программы — тем более пишите, постараюсь помочь во всём.

    Бонус: немного графиков по результатам анализа моей коллекции
    Медиана частоты №10 из 31 против крутизны


    Медиана частоты №10 из 31 против скоса


    Медиана частоты №10 из 31 против стандартного отклонения


    Крутизна частоты №10 из 31 против скоса (обычная зашумлённая парабола, не так ли?)


    Гистограмма распределения среднего и медианы по левой оси и стандартного отклонения по правой


    Пример среднего значения по всем частотам (делалось для базы по 100 частотам, отнормировано по среднему значению)


    График сглаженного значения скоса по всем частотам (100 частот, отнормировано по среднему значению)

    Share post
    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More
    Ads

    Comments 39

      +3
      Это очень круто.
      Развитие идеи, которое даст более широкое применение. Все мы прекрасно знаем, что разные песни хочется слушать под какое-то определенное настроение. Медленные рок-баллады или динамичный панк.
      Если модифицировать программу вот так:
      1) пользователь выбирает самые яркие представители того или иного настроения
      2) программа ищет уже не к одной песни, а сразу к пачке (что повышает точность выходного материала) похожие песни
      3) проставляет id3-теги, на радость программам, вроде MediaMonkey
      … то будет реально крутая штука для меломанов.
        +3
        На самом деле очень классная и полезная вещь.
        То, что программа не всегда находит песни того же исполнителя — вообще не проблема, так как это легко можно сделать введя имя этого исполнителя в поиск (а если уж вы исполнителя не знаете — Shazam в помощь).
        Вы вполне можете начать стартап — такая штука очень даже будет востребованна.
          0
          Проблема в том, что казалось бы, наиболее близкими «по духу» должны быть вещи с того же альбома того же исполнителя, но поскольку программа пока не справляется с их выявлением это значит что точность поиска нужно увеличивать.
            0
            Проблема в том, что казалось бы, наиболее близкими «по духу» должны быть вещи с того же альбома того же исполнителя

            ИМХО, совсем не обязательно. Очень часто, когда есть определённое настроение (внимательно читать, расслабиться или, например, работать), выдёргиваю в плейлист на 2-3 композиции из разных альбомов, разных групп и перемешиваю. Ваша программа поможет делать это автоматом :)
          0
          Уже можно задавать в качестве образца пачку песен.
          0
          Мне очень понравилось. Запустил исходники, посмотрел, вопрос такой — а есть ли многопоточность? Скажем, пытались ли распараллеливать?
            0
            Пока многопоточности нет, но думаю что это позволит ускорить формирование БД. Есть только опасения за блокировки при одновременной записи в БД, не знаю как SQLite с этим справляется.
            0
            Скачал бинарники. После задания директории с музыкальной коллекцией и нажатия на кнопку gather stats не происходит ничего. Программа зависает в состоянии not responding. Подождал минут 20 и закрыл ее таск менеджером.
              0
              Приношу свои извинения. Программа действительно получилась пока больше как proof-of-concept, но мне очень хотелось поскорее поделиться результатами :)
                0
                Вам спасибо за попытку. Пока что пользуюсь для данной цели плагином под foobar, который ищет похожести на основе их базы данных. Буду очень рад, когда Ваша программа заработает, ибо тону в террабайте с любовью отобранной за 20 лет музыки.
                  0
                  Насчёт «тону в терабайте» — аналогично, потому и затеял проект.
                    0
                    А вообще, если вы указали в качестве корня весь диск (C или D или ещё какой-то), то поиск всех mp3 может занять ощутимое время. Попробуйте дождаться. Впрочем, возможно будет лучше дождаться следующей версии ;)
                    0
                    Это надо в отдельный поток вынести. Пусть сам трудится — тогда основной UI зависать не будет…
                  0
                  На гитхабе отсутсвует папка Properties
                    0
                    На самом деле программа очень сырая. Вся логика в Form1.cs :)
                    +12
                    Напишите во Вконтакте. Вас возьмут на работу и предоставят 100500 серверных мощностей, а мы сможем подбирать себе композиции по умному алгоритму :)
                      0
                      Вы правы, для пользователей вконтакте это была бы полезная функция, вопрос в том как эту функцию встроить в бизнес-план ВК. Не думаю что Дуров и ко. большие филантропы.
                      0
                      это называется sound fingerprint. Кому интересно могут погуглить проекты на эту тему.
                        0
                        Совершенно верно. Даже у Youtube есть функция мэтчинга использованных саундтреков, но при плотном изучении литературы по теме, я выяснил что исследователи ставили задачу больше как «Классифицировать композицию по настроению весёлая/грустная/агрессивная/вялая», а в плане поиска именно близких к образцу элементов — практически ничего нет.
                          0
                          Можете поделиться ссылками? По факту им гораздо важнее определять наличие лицензионного контента, например, на мое подобранное на слух и по нотам исполнение Jim Brickman повесили предупреждение «Matched third party content» и показывают рекламу именно на этом видео, прибыль видно идет правообладателю. То есть они как раз нашли похожую запись, при том что естественно все отличается и темп и инструменты и т.д.
                            0
                            Много интересного находится гуглением в лоб. Собственно, все эти доки я и вычитывал.
                            Насчёт поиска по подобранному на слух — вполне возможно, я ведь далеко не первый кто пришёл к мысли поиска подобных композиций, просто в ютубе ребята настроили поиск на выявление мелодий, а не настроения.
                        0
                        Можно ли модифицировать программу для поиска оригиналов каверов/ремиксов/etc?

                        Грубо говоря имеется база из относительно небольшого числа гарантированно разных оригиналов.
                        На вход программе подается некий трек, программа должна угадать оригинал.

                        Вышла бы ультимативная разгадывалка Touhou-треков.
                          0
                          Насколько я понимаю термин «кавер», то от исходной композиции там может практически ничего не остаться. Сравните например «Whiskey in a Jar» в исполнении Metallica и какого-нибудь ирландского народного коллектива. Мелодия общая, но это будет совсем «не в духе».
                            0
                            Полагаю, для распознования каверов нужно распозновать текст и сравнивать по нему. Довольно сложная задача.
                          +1
                          Хорошее начинание)
                          Вот только хотелось бы поддержки форматов помимо mp3.
                            0
                            Работаю в этом направлении.
                            0
                            Такую бы программу, ориентированную на электронную музыку, для поиска подходящих под настроение треков.
                              0
                              Эмбиент как часть электронной музыки уже сейчас ищется по настроение прекрасно.
                              Насчёт техно/хауса/дабстепа/что там сейчас ещё модно — надо пробовать, у меня их выборка нерепрезентативна.
                              0
                              Что-то у меня программа даже и не заработала (как заранее скопиленная, так и из исходников)

                              pastebin.com/LvAZiMjT

                              Похоже, что программа пытается из пустой базы получить данные
                                0
                                Это очень странно. Сначала составляется список mp3-файлов по указанному вами пути, затем дропаются все нужные таблицы и затем идёт создание их заново.
                                После каких действий возникла ошибка? Если можно — давайте в ЛС перейдём, чтобы не засорять комментарии. Спасибо.
                                  0
                                  Да кажется проблема решена. Интерфейс, конечно, не совсем очевидный. Не догадался во вкладку create database зайти)
                                0
                                Поскольку ещё никто не написал, посоветую похожий проект — Pandora Internet Radio, www.pandora.com хоть там подборка музыки ведётся и не по автоматическому анализу, а по тегам, которые добровольцы сидели и подбирали для огромного количество трэков. Однако результаты — феноменальные. Отчасти потому что в тегах они используют не только малоописывающие факты типа года записи или номера трэка на пластинке, а вещи типа «минимальное использование саскофона», «основной инструмент бас-гитара», «частое изменение темпа» или даже «тональность Em» и т.д. И все эти факторы умно подбираются так что действительно находится огромное количество по-настоящему похожих трэков.

                                К сожалению, пару лет назад в штатах запретили вещание в других странах (потому что сервис не только подбирает музыку, а ещё и сразу проигрывает её), поэтому чтобы послушать вам понадобится vpn, vps или даже tor с правильно сконфигурированым exit nodом.

                                Было бы интересно посмотреть во что может вылиться ваш проект, но пока честно говоря не очень верится что в ближайшие годы полностью автоматический алгоритм сможет переплюнуть пандору, там столько человечно-субъективных тегов…
                                В любом случае, желаю удачи вашему проекту.
                                  0
                                  Спасибо вам.
                                  Про Пандору наслышан, это действительно отличный проект, сильной стороной которого является участие человека в классификации.
                                  Но во-первых, это будет база Пандоры, а не ваша собственная, нажитая годами и облюбованная :) И потом, не думаю, что у Пандоры сколь-нибудь достойно представлена андеграундная музыка.
                                  0
                                    0
                                    Из трех проектов, с похожей функциональностью (jango, last.fm, pandora) последняя на голову выше конкурентов по качеству подбора. Желаю вам добиться тех же высот.
                                      0
                                      Спасибо!
                                      Думаю тренированный эксперт ещё очень долго будет лучше любого машинного алгоритма. Только эксперта надо найти, нанять и кормить платить ему зарплату :)
                                      0
                                      А как оно по сравнению с известными реализациями?

                                      Only users with full accounts can post comments. Log in, please.