Інформаційна технологія пошуку заданих фрагментів в архіві аудіозаписів із застосуванням kd-дерев

Abstract

Дисертаційну роботу присвячено підвищенню повноти і релевантності результатів та швидкості пошуку за рахунок розроблення інформаційної технології пошуку заданих фрагментів в архіві аудіозаписів із застосуванням kd- дерев. З розвитком Інтернету, цифрових ЗМІ, мультимедійних технологій та можливістю доступу до великих архівів мультимедіа виникла необхідність створення нових способів навігації та взаємодії з цими архівами аудіозаписів. Незважаючи на великі успіхи, досягнуті у цій галузі в останні роки, сучасним інформаційно-пошуковим системам притаманні певні недоліки, зокрема: - недостатня продуктивність під час роботи з великими архівами; - неможливість їхнього безпосереднього застосування для розв’язання таких задач, як моніторинг трансляції на радіостанціях (телебаченні) для визначення кількості повторень в ефірі рекламного продукту, музичного твору тощо. Запропоновано модель корпусу аудіозаписів, яка містить масив файлів, базу параметрів та метаданих і динамічне kd-дерево, що дозволило зменшити тривалість обраного для пошуку аудіофрагмента та реалізувати інформаційну технологію пошуку аудіозаписів з різною тривалістю звучання. Показано, що мінімальна тривалість аудіофрагмента, яка забезпечує повноту результатів пошуку аудіозапису 99,4%, має складати 1 с. Отримав подальшого розвитку метод кластеризації k-середніх, який відрізняється від існуючих удосконаленою процедурою відбору вектора на позицію вставки нового центроїда шляхом послідовного запуску методу k- середніх, що дозволяє отримати розв’язок, наближений до глобального мінімуму похибки кластеризації. Удосконалено метод пошуку на основі kd-дерева, який, на відміну від існуючих, використовує оцінку міри близькості за зваженою кількістю потраплянь в список найближчих центроїдів, що дозволяє підвищити повноту та релевантність результатів пошуку. Запропоновано метод комбінованого пошуку аудіозапису за заданим аудіофрагментом, який базується на виконанні швидкого наближеного пошуку у базі параметрів зменшеної розмірності із застосуванням kd-дерева кількох найближчих аудіозаписів на першому етапі пошуку, серед яких на другому етапі відбувається вибір релевантного аудіозапису, що дозволило досягти зменшення часу пошуку порівняно з точним пошуком на основі kd-дерева. На основі результатів теоретичних досліджень розроблено інформаційну технологію пошуку заданих аудіофрагментів в архіві аудіозаписів, яка містить: алгоритм та програму для реалізації методу кластеризації на основі послідовного запуску k-середніх з удосконаленим вибором вектора на позицію вставки нового центроїда; алгоритм та програму пошуку заданого аудіофрагмента на основі математичного очікування похибки кластеризації; алгоритм та програму швидкого пошуку на основі kd-дерев; методику використання системи автоматичного пошуку аудіозаписів. Запропоновані методи та розроблені на їхній

24

основі алгоритми та програмні засоби дозволяють проводити пошук заданого аудіофрагмента у реальному масштабі часу. Результати досліджень впроваджено в Інституті електроніки та зв'язку Української академії наук, а також у навчальний процес у Вінницькому національному технічному університеті з дисципліни "Цифрова обробка сигналів".

Диссертация посвящена повышению полноты и релевантности результатов и скорости поиска за счет разработки информационной технологии поиска заданных фрагментов в архиве аудиозаписей с применением kd-деревьев. С развитием Интернета, цифровых СМИ, мультимедийных технологий и возможностью доступа к большим архивам мультимедиа возникла необходимость предложить новые способы навигации и взаимодействия с этими архивами аудиозаписей. Несмотря на большие успехи, достигнутые в этой области в последние годы, современным информационно-поисковым системам присущи определенные недостатки, в частности: - недостаточная производительность при работе с большими архивами; - невозможность их непосредственного применения для решения таких задач, как мониторинг трансляции на радиостанциях (телевидении) для определения количества повторений в эфире рекламного продукта, музыкального произведения и т. д.Предложенные методы и разработанные на их основе алгоритмы и программные средства позволяют проводить поиск заданного аудиофрагмента в реальном масштабе времени. Результаты исследований внедрены в Институте электроники и связи Украинской академии наук, а также в учебный процесс в Винницком национальном техническом университете по дисциплине "Цифровая обработка сигналов".

The Dissertation is devoted to improving recall and precision of the search results and increasing the speed on the basis of information technology for search of the specified audio fragments in the archive of audio recordings using kd-tree. With the development of the Internet, digital media, multimedia technology and access to the large multimedia archives became necessary to create new ways of navigation and interaction with the audio archives. Despite the great progress achieved in this area in the recent years, modern information retrieval systems have some shortcomings, in particular: - the insufficient performance with regard to the large archives; - the impossibility of the direct application to solve such tasks as broadcast monitoring on the radio (television) to determine the repetition number of some audio recording (e.g. an advertising product, a musical piece, etc.) during translation. The offered model of the audio body, which contains an array of audiofiles, a database of parameters and metadata, and dynamic kd-tree, allowed to reduce the audio fragment duration, selected for the search, and implement information technology for search of audio recordings with the different duration. It is shown that the lowest duration of the audio fragment that ensures the recall of the search results at 99.4%, should be 1s. The method of k-means clustering got the further development, differs from the existing ones by the improved procedure of selecting the vector as a new centroid by successive run of k-means that provides a solution, close to the global minimum of the clustering error. The search method based on kd-tree is improved, which unlike the existing, uses the improved estimation of the measure proximity, enhancing the rallback and precision of search results. The method of the combined search of audio recording for a specified audio fragment is proposed, based on the implementation of the fast approximate kd-tree search of the several nearest recordings in the parameter database of the reduced dimension on the first stage of the search, among them the relevant audio recording is defined on the second stage, which resulted in reducing the time search compared to an accurate kd-tree search.The proposed methods, as well as algorithms and software, developed on their basis, allowed to search the specified audio fragment in real time. The research results implemented at the Institute of Electronics and Communications of the Ukrainian Academy of Sciences and in the educational process of VNTU at the course "Digital Signal Processing".