Метод підвищення швидкості пошуку фрагменту аудіозапису із застосуванням KD-дерев

Abstract

Стаття присвячена розв'язанню задачі ідентифікації музичного твору за коротким фрагментом. В статті запропоновано метод пошуку найближчого шаблону 5с аудіофрагменту на основі kd-дерева, що дозволив значно зменшити складність обчислень порівняно з повним пошуком. Для виконання швидкого пошуку на основі kd-дерева в попередньо сформованому корпусі шаблонів розроблено алгоритмічне та програмне забезпечення. Запропоновано аналітичне співвідношення для оцінювання близькості невідомого фрагменту з шаблонами, яке базується на обчисленні відстані від фрагменту до заданої кількості найближчих центроїдів.

Статья посвящена решению задачи идентификации музикального произведения по короткомуфрагменту. В статье предложен метод поиска ближайшего шаблона 5с аудиофрагмента на основе kd-дерева, который позволил значительно уменшить сложность вычислений по сравнению с полным поиском. Для выполнения бистрого поиска на основе kd-дерева в предварительно сформированном корпусе шаблонов разработано алгоритмическое и программное обеспечение. Предложено аналитическое соотношение для оценки близости неизвестного фрагмента с шаблонами, основанное на вычислении расстояния от фрагмента с заданным числом ближайших центроидов.

The article is devoted to solving the problem of audio identification by the short fragment. The method of the nearest template search for audio fragment (5s) based on kd-tree was proposed in the paper, which allowed to reduce the computational complexity significantly compared to full search. To perform a quick search based on kd-tree in pre-formed body of templates algorithms and software were developed. Analytical relation for evaluating the proximity between the unknown fragment and templates was proposed, which is based on calculating the distance from the fragment to the specified number of the nearest centroids.