Система и способ для ускорения поисков в базе данных для множественных синхронизированных потоков данных

Изобретение относится к идентификации объектов аудиовизуальной информации в потоках вещаемой аудиовизуальной информации. Техническим результатом является повышение быстродействия сервера за счет эффективного предоставления услуг по идентификации, одновременно, большему числу пользователей. В способе осуществляют передачу каждому из множества компьютеров-клиентов, на постоянной основе, сгенерированные клиентом «следы» потока аудиовизуальной информации; для каждого переданного «следа» используют сервер для поиска в кэше «следов» совпадающего «следа» для этого «следа»; причем каждый «след» в кэше «следов» содержит заранее заданное время существования, и при этом любой «след», время существования которого истекло, удаляется из кэша «следов» вместе с любой связанной с ним идентификационной информацией об объекте аудиовизуальной информации; в случае если база данных «характерных отпечатков» содержит совпадающий «характерный отпечаток», передают из сервера соответствующему клиенту идентификационную информацию об объекте аудиовизуальной информации, связанную с этим «характерным отпечатком». 3 н. и 21 з.п. ф-лы, 4 ил.

 

Область техники, к которой относится изобретение

Изобретение относится к идентификации объектов аудиовизуальной информации в потоках вещаемой аудиовизуальной информации, и, в частности, к системе и способу для обеспечения одновременной производимой на сервере идентификации объектов аудиовизуальной информации, таких как песни, в синхронизированных потоках данных, для большого количества индивидуальных клиентов, при минимизации поисковой нагрузки на базу данных сервера.

Уровень техники

Существует множество схем для выделения «признаков» из сигнала для их использования в целях идентификации. Например, в том, что касается одномерного сигнала, такого как аудиосигнал или файл аудиоданных, то выделение аудиопризнака использовалось в качестве необходимого этапа для решения задач классификации, поиска и идентификации в отношении объектов аудиовизуальной информации в аудиосигнале. Для идентификации выделенные признаки или «следы» обычно сравниваются с известным «характерным отпечатком» с тем, чтобы идентифицировать либо элементы в составе аудиосигнала, либо весь аудиосигнал. Такие хорошо известные схемы идентификации объектов аудиовизуальной информации традиционно известны под наименованием «снятие характерных отпечатков аудиосигнала».

В целом ряде традиционных схем такие технологии «снятия характерных отпечатков» аудиосигнала были приспособлены для обеспечения идентификации конкретных песен в потоке аудиоданных, таком как радио- или Интернет-вещание. Например, пользователь, слушающий поток аудиоданных, может услышать некоторую песню, о которой он или она хотел бы узнать: наименование, исполнителя, альбом и т.д. В таком случае традиционные технологии «снятия характерных отпечатков аудиосигнала» используются для выделения одного или более «следов» из образцов, взятых из этой песни. Обычно, эти «следы» затем сравниваются с характерными отпечатками, хранящимися в базе данных известных музыкальных произведений, с тем, чтобы идентифицировать совпадение, причем, результаты этого затем предоставляются пользователю.

Кроме того, такие технологии также были приспособлены к ряду традиционных услуг с целью предоставления на платной основе услуги по идентификации или поиску песен, которая обычно основывается на технологиях «снятия характерных отпечатков аудиосигнала» и сравнениях с базой данных. Например, для идентификации конкретных песен для пользователей, осуществляемой через сеть сотовой телефонной связи, функционирует несколько служб идентификации песен, таких как относительно хорошо известная служба идентификации музыкальных произведений «Shazam». В частности, системы, такие как система, предлагаемая «Shazam», обычно функционируют таким образом, что сначала требуют от пользователя набрать некоторый номер на его телефонном аппарате сотовой связи, а затем удерживать этот телефонный аппарат направленным на источник музыки в течение приблизительно от 15 до 30 секунд. После этого служба «Shazam» идентифицирует музыкальное произведение, сравнивая это музыкальное произведение (или «следы», вычисленные на основе этого музыкального произведения) с базой данных известных музыкальных произведений. После этого служба «Shazam» возвращает пользователю текстовое сообщение, содержащее наименование, данные об исполнителе, альбоме и тому подобную информацию об идентифицированной песне.

К сожалению, одна из проблем с поисковыми службами вышеописанного типа заключается в том, что по мере того, как увеличивается количество пользователей, осуществляющих доступ к системе идентификации музыкальных произведений в любой данный момент времени, количество запросов на поиск в базе данных, приходящееся на одну секунду, также увеличивается. Эта проблема смягчается, например, в случае таких услуг, как услуги, предоставляемые службой «Shazam», поскольку пользователь должен оплачивать телефонный звонок и саму эту услугу за каждую песню, которую он желает идентифицировать, поскольку результат взимания такого рода платы с пользователей имеет тенденцию ограничивать количество одновременных пользователей системы, тем самым сокращая общую нагрузку на сервер. Другая проблема с такого рода системой заключается в том, что она требует, чтобы образцы полной песни (находящиеся под действием ограничений по частоте/ширине полосы, накладываемых телефонной службой) передавались на сервер, от которого затем требуется вычислить «следы», на основе переданного образца потока аудиовизуальной информации.

Следовательно, по мере того, как количество одновременно обращающихся пользователей становится во все возрастающей степени большим, вычислительная нагрузка при вычислении «следов» или «характерных отпечатков» на основе поступающих музыкальных произведений, проведении поисков в базе данных с целью идентификации этих «характерных отпечатков» и дачи ответа индивидуальным пользователям может быстро вызвать перегрузку даже относительно больших групп специализированных серверов. В результате существует тенденция ограничивать такие схемы допущением того, что количество одновременно обращающихся пользователей будет относительно низким. Кроме того, хотя существует возможность нарастить такие схемы с тем, чтобы обеспечить достаточное количество серверов для работы с большим количеством одновременно обращающихся пользователей, потенциально исчисляемого десятками миллионов пользователей, денежные затраты на такую систему вероятно будут непомерно высоки.

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

Раскрытие изобретения

«Средство идентификации аудиовизуальной информации», в том виде, в котором оно описано в данном описании, функционирует таким образом, чтобы решить вышеописанные проблемы, обеспечивая индивидуальным клиентам осуществляемую в реальном масштабе времени на стороне сервера идентификацию объектов аудиовизуальной информации, включенных в вещание потоковой аудиовизуальной информации, такого как, например, радио-, телевизионное или Интернет-вещание. Эти объекты аудиовизуальной информации включают в себя, например, песни, рекламные ролики, музыкальные заставки, позывные станций и т.д. Вообще, это Средство идентификации аудиовизуальной информации функционирует, предоставляя, по меньшей мере, один сервер, который обеспечивает осуществляемую в реальном масштабе времени идентификацию объектов аудиовизуальной информации в потоке вещаемой аудиовизуальной информации, для индивидуальных клиентов, посредством сравнения «следов», вычисляемых каждым клиентом на основе частей потока аудиовизуальной информации, взятых в качестве образцов, с базой данных известных «характерных отпечатков». Вообще, вычисленные «следы» посылаются каждым клиентом на сервер и сравниваются либо напрямую, либо через имеющийся на стороне сервера кэш «следов», с большой базой данных хранящихся заранее вычисленных «следов» (именуемых в данном документе «характерными отпечатками», чтобы отличать их от «следов», сгенерированных клиентом), идентификационные данные которых известны.

В частности, для каждого клиента сегменты фиксированной длины из поступающего потока аудиовизуальной информации используются для вычисления через повторяющиеся промежутки времени «следов», имеющих малую размерность. В протестированном варианте осуществления изобретения такие «следы» вычислялись и посылались каждым клиентом примерно около шести раз в секунду на основе образцов потока аудиовизуальной информации, имеющих длительность приблизительно шесть секунд. Очевидно, что может быть использовано большее или меньшее количество «следов», использующих более длинные или более короткие продолжительности образцов, причем, эти параметры обычно зависят от конкретных технологий, используемых для вычисления «следов».

Вычисление «следов» на основе потока аудиовизуальной информации выполняется с использованием традиционных технологий, таких как, например, система, описанная в публикации заявки на патент США, имеющей номер US 2003/0236661 и озаглавленной «System and Method for Noise-Robust Feature Extraction» («Система и способ для шумоустойчивого выделения признака»), содержание которой включено в настоящее описание посредством этой ссылки. Вообще, такие системы функционируют, беря образцы из поступающего потока аудиовизуальной информации и вычисляя на основе взятого в качестве образца сигнала векторы-признаки малой размерности (то есть, «следы»). Вычисление «следа» на основе подвергаемых взятию образцов потоков аудиовизуальной информации известно специалистам в данной области техники и не будет здесь описываться подробно.

«Характерные отпечатки», составляющие базу данных «характерных отпечатков», обычно вычисляются тем же самым способом, что и «следы», используя те же самые алгоритмы. Однако в отличие от «следов» «характерные отпечатки» вычисляются только один раз на основе одного или более образцов каждого известного объекта аудиовизуальной информации с тем, чтобы сформировать базу данных известных «характерных отпечатков». Будучи один раз созданной, эта база данных затем просто является объектом доступа со стороны сервера без необходимости повторного вычисления «характерных отпечатков» для известных объектов аудиовизуальной информации. Однако база данных известных «характерных отпечатков» может впоследствии обновляться с внесением в нее новых «характерных отпечатков» по мере того, как создаются новые объекты аудиовизуальной информации (песни и т.д.). По этой причине предпочтительно, чтобы база данных известных «характерных отпечатков» создавалась в автономном режиме и после этого просто предоставлялась серверу, так чтобы устранить любую дополнительную вычислительную нагрузку на сервер во время операций идентификации аудиовизуальной информации, исполняемых описанным здесь Средством идентификации аудиовизуальной информации.

После этого для каждого клиента сервер использует неточное отождествление для того, чтобы определить, совпадает ли какой-либо из «следов» с каким-либо из «характерных отпечатков» в базе данных в пределах некоторой пороговой величины или допуска. Использование таких технологий неточного отождествления является предпочтительным по сравнению с технологиями точного отождествления, поскольку «следы», вычисленные какими-либо из клиентов, могут различаться вследствие шума, помех, ослабления сигнала и т.д. даже в том случае, когда «следы» вычислены на основе в точности тех же самых частей потока аудиовизуальной информации. Кроме того, использование неточного отождествления также учитывает небольшие временные смещения во взятых как образцы частях потока аудиовизуальной информации, на основе которых были вычислены «следы». В одном варианте осуществления изобретения неточное отождествление использует для повышения точности перенормализацию по «характерному отпечатку», что известно в данной области техники и, например, описано в публикации, озаглавленной «Distortion Discriminant Analysis for Audio Fingerprinting» («Распознающий искажения анализ для снятия «характерных отпечатков»»), которая имеет своими авторами: Кристофера Дж. К. Берджеса (Christopher J. C. Burges), Джона К. Платта (John C. Platt) и Соумя Джана (Soumya Jana), опубликована в IEEE Transactions on Speech and Audio Processing (Трудах Института инженеров по электротехнике и радиоэлектронике, раздел «Обработка речи и аудиоинформации»), а именно IEEE Transactions on Speech and Audio Processing, Том 11, № 3, страницы 165 - 174, май 2003 г., и содержание которой включено в настоящее описание посредством этой ссылки.

Всякий раз, когда «след», полученный от какого-нибудь клиента, совпадает с «характерным отпечатком», сервер сообщает этому клиенту идентификационные данные конкретного объекта аудиовизуальной информации, соответствующего этому «следу». В случае таких объектов аудиовизуальной информации, как песни, эти идентификационные данные обычно включают в себя такую информацию, как, например, исполнитель, наименование песни, наименование альбома, жанр и т.д. Очевидно, что если объект аудиовизуальной информации известен, то с «характерными отпечатками» в базе данных, которые используются для идентификации этого объекта аудиовизуальной информации, может быть связана любая необходимая информация.

Однако вместо того, чтобы проводить требующий больших усилий поиск в базе данных «характерных отпечатков» по каждому «следу», присланному на сервер, описанное здесь Средство идентификации аудиовизуальной информации вводит дополнительный расположенный на стороне сервера кэш, который использует тот факт, что в любой момент времени многие из сгенерированных пользователями «следов», вероятно, являются почти идентичными, если предположить, что имеется ограниченное количество потоков аудиовизуальной информации, и что обычно в любой данный момент времени имеется большое количество пользователей, принимающих один и тот же поток аудиовизуальной информации. Иначе говоря, в любой данный момент времени вероятно, что имеется множество, потенциально десятки тысяч или даже миллионы, людей, слушающих один и тот же поток аудиовизуальной информации, такой как конкретные вещательные передачи радио-, телевизионного или Интернет-вещания. Это наблюдение позволяет создать на стороне сервера кэш, который кэширует как поступающие «следы», так и результаты поиска в базе данных на предмет совпадающих с ними «характерных отпечатков».

В частности, каждый поступающий от каждого клиента «след» сначала проверяется по кэшу, который содержит в себе некоторое количество «следов». Если этот «след» в кэше отсутствует, то производится поиск в полной базе данных, и результаты этого поиска в базе данных как положительные, так и отрицательные, сохраняются в кэше вместе со «следом», присланным клиентом. Поиски как в кэше, так и в базе данных могут выполняться с использованием традиционных технологий, таких как, например, линейный перебор (то есть, последовательно) с наложением ограничений (известный способ ускорения сравнений отклонений с использованием линейного перебора).

В другом варианте осуществления изобретения поиски в базе данных ускорены за счет использования битового векторного индексирования, что описано в заявке на патент США, которая находится на рассмотрении одновременно с данной заявкой, озаглавлена «Multidimensional Data Object Searching Using Bit Vector Indices» («Поиск объектов многомерных данных с использованием битовых векторных индексов»), имеет дату подачи 23 июня 2003 года и присвоенный ей порядковый номер 10/602,438, и содержание которой включено в настоящее описание посредством этой ссылки. Этот подход, заключающийся в битовом векторном индексировании, также описан в публикации, которая озаглавлена «Indexing High Dimensional Rectangles for Fast Multimedia Identification» («Индексирование многомерных прямоугольников для быстрой идентификации мультимедиа»), имеет своими авторами Джона К. Платта (John C. Platt) и Кристофера Дж. К. Берджеса (Christopher J. C. Burges), опубликована в Microsoft Technical Report (Технический отчет компании «Microsoft») MSR-TR-2003-38, датированном 28 октября 2003 г., и содержание которой включено в настоящее описание посредством этой ссылки.

Вообще, способы битового векторного индексирования, описанные в вышеупомянутых заявке на патент США и соответствующем Техническом отчете компании «Microsoft», рассматривают проблему быстрого осуществления точечных запросов в отношении многомерных областей. Такие запросы полезны при решении становящихся все более важными задач идентификации и поиска мультимедиа, в которых различные элементы базы данных имеют различные показатели сходства. В противоположность обычному индексированию в базе данных, которое сосредоточено на индексировании для многомерных запросов о ближайшем соседнем элементе и эпсилон-интервале, индексирование для точечных запросов в отношении многомерных областей, предоставляет эффективный способ индексирования, в котором для достижения значительных выигрышей в производительности сделана ставка на сочетание избыточности и битового векторного индексирования. Было отмечено, что такие способы обеспечивают значительное повышение производительности по сравнению с характерными для реального мира способами линейного перебора.

Отрицательные результаты поиска в базе данных, то есть данные об отсутствии совпадения «следа» с «характерными отпечатками» в базе данных, не посылаются назад клиенту. Положительные результаты поиска в базе данных, то есть данные о совпадении «следа» и «характерного отпечатка», посылаются назад клиенту, чтобы идентифицировать объект аудиовизуальной информации, на основе которого был вычислен этот «след». Как отмечалось выше, поиск в кэше с целью идентифицировать совпадающие «следы» осуществляется перед поиском в базе данных «характерных отпечатков». Следовательно, если обнаружено совпадение со «следами», хранящимися в кэше, то не требуется никакого последующего поиска в базе данных, поскольку «след», хранящийся в кэше, будет либо содержать идентификационные данные связанного с ним объекта аудиовизуальной информации, либо будет просто указывать, что совпадающий «характерный отпечаток» отсутствует. В случае, когда «след» совпадает с «характерным отпечатком» в базе данных, назад клиенту будет послана любая идентификационная информация, связанная с этим совпадающим «характерным отпечатком».

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

В частности, каждый конкретный поток вещания аудиовизуальной информации приблизительно синхронизирован по каждому клиенту, который принимает этот конкретный поток аудиовизуальной информации. Например, любые два или более клиентов, принимающих одну и ту же радиостанцию, вероятно, принимают один и тот же сигнал в пределах очень небольшого временного смещения примерно около одной секунды или около того. То же самое верно также и для большинства вещательных передач потоковой аудиовизуальной информации Интернет- или сетевого вещания.

По этой причине нет необходимости держать «следы» в кэше аудиовизуальной информации в течение промежутка времени, превышающего некоторое малое кратное максимального ожидаемого времени задержки (причем, время задержки также включает в себя максимальную ожидаемую задержку по каждому клиенту на вычисление и передачу «следа» на сервер). Иначе говоря, эта задержка представляет собой просто максимальное значение времени между приемом сервером первого «следа» для данной части конкретного объекта аудиовизуальной информации и приемом сервером последнего «следа» (от самого медленного клиента) для этой части того же самого объекта аудиовизуальной информации. Следовательно, следы необходимо держать в кэше только в течение короткого промежутка времени длительностью примерно несколько секунд. В результате отсутствует необходимость в большом кэше для хранения всех уникальных поступающих на сервер «следов».

В родственном варианте осуществления изобретения, вместо попыток определить или оценить максимальные значения времени задержки для установления сроков жизни «следов» в кэше, предлагается более простое решение, которое заключается в том, чтобы просто удалять «следы» из кэша после того, как они не совпали ни с какими поступающими «следами» в течение некоторого короткого промежутка времени длительностью примерно в одну секунду или около того. В дополнительных альтернативных вариантах осуществления изобретения также могут быть использованы другие схемы кэширования, включая, например, использование фиксированного размера кэша, который удаляет «следы» основываясь на традиционной логике удаления элементов с наиболее давним использованием.

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

Перечень фигур чертежей

Конкретные признаки, аспекты и преимущества настоящего изобретения станут более понятны при рассмотрении нижеследующего описания, прилагаемой формулы изобретения и сопровождающих их чертежей, на которых:

Фиг.1 - общая схема системы, изображающая вычислительное устройство общего назначения, которое составляет приводимую в качестве примера систему, реализующую «Средство идентификации аудиовизуальной информации» в том виде, как оно описано в данном документе.

Фиг.2 - приводимая в качестве примера структурная схема системы, которая иллюстрирует общее отношение между функциональными компонентами для реализации «Средства идентификации аудиовизуальной информации» в том виде, как оно описано в данном документе.

Фиг.3 - приводимая в качестве примера укрупненная блок-схема алгоритма, которая иллюстрирует программные модули для реализации «Средства идентификации аудиовизуальной информации» в том виде, как оно описано в данном документе.

Фиг.4 - блок-схема последовательности операций, которая иллюстрирует общее функционирование одного варианта осуществления Средства идентификации аудиовизуальной информации в том виде, как оно описано в данном документе.

Осуществление изобретения

В нижеследующем описании предпочтительных вариантов осуществления настоящего изобретения делается ссылка на прилагаемые чертежи, которые образуют часть этого описания и на которых в порядке иллюстрации показаны конкретные варианты осуществления, в которых это изобретение может быть практически реализовано. При этом понимается, что могут быть использованы и другие варианты осуществления изобретения, и в изобретение могут быть внесены структурные изменения, что не выходит за пределы объема настоящего изобретения.

1.0 Приводимая в качестве примера операционная среда:

На Фиг.1 проиллюстрирован пример подходящей вычислительной системной среды (100), в которой может быть реализовано данное изобретение. Вычислительная системная среда (100) представляет собой только один пример подходящей вычислительной среды и не имеет своей целью предложить какое-либо ограничение в отношении объема использования или функциональных возможностей изобретения. Равным образом вычислительная среда (100) не должна толковаться как имеющая какую-либо зависимость или требование, относящиеся к какому-либо компоненту или сочетанию компонентов, проиллюстрированных в приводимой в качестве примера операционной среде (100).

Изобретение способно работать и с многочисленными другими вычислительными системными средами или конфигурациями. Примерами хорошо известных вычислительных систем, сред и/или конфигураций, которые могут быть пригодны для использования с данным изобретением, включают в себя, но не в смысле ограничения, персональные компьютеры; компьютеры-серверы; переносной, портативный или мобильный компьютер или устройства связи, такие как телефонные аппараты сотовой связи и персональные цифровые секретари (PDA); многопроцессорные системы; системы, основанные на микропроцессорах; блоки управления; программируемая бытовая радиоэлектронная аппаратура, сетевые персональные компьютеры (РС), мини-компьютеры, универсальные компьютеры, распределенные вычислительные среды, которые включают в себя любые из вышеописанных систем или устройств и тому подобное.

Изобретение может быть описано в общем контексте машиноисполняемых команд, таких как программные модули, исполняемые компьютером, в сочетании с модулями аппаратного обеспечения, включающих в себя компоненты матрицы (198) микрофонов. Обычно, программные модули включают в себя процедуры, программы, объекты, компоненты, структуры данных и т.д., выполняющие конкретные задачи или реализующие определенные абстрактные типы данных. Изобретение также может быть практически реализовано в распределенных вычислительных средах, в которых задачи выполняются удаленными устройствами обработки данных, связанными через сеть связи. В распределенной вычислительной среде программные модули могут быть размещены как в локальных, так и в удаленных компьютерных носителях информации, включая запоминающие устройства. Согласно Фиг.1 приводимая в качестве примера система для реализации изобретения содержит вычислительное устройство общего назначения в виде компьютера (110).

Компоненты компьютера (110) могут содержать, но не в ограничительном смысле, процессор (120), системную память (130) и системную шину (121), которая соединяет различные компоненты системы, включая системную память, с процессором (120). Системная шина (121) может относиться к любому из нескольких типов структур шины, включая шину памяти или контроллер памяти, периферийную шину и локальную шину, использующие любую из множества архитектур шины. В качестве примера, но не ограничения, такие архитектуры включают в себя шину архитектуры отраслевого стандарта (ISA), шину микроканальной архитектуры (МСА), усовершенствованную шину ISA (ЕISA), локальную шину Ассоциации по стандартам в области видеоэлектроники (VESA) и шину межсоединения периферийных компонентов (PCI), также известную как мезонинная шина.

Компьютер (110) обычно содержит разнообразные машиночитаемые носители информации. Машиночитаемые носители информации могут представлять собой любые доступные носители информации, к которым может осуществлять доступ компьютер (110), и включают в себя как энергозависимые, так и энергонезависимые носители информации, как съемные, так и несъемные носители информации. В качестве примера, но не ограничения, машиночитаемые носители информации могут включать в себя компьютерные носители информации и среду передачи данных. Компьютерные носители информации включают в себя энергозависимые и энергонезависимые, съемные и несъемные носители информации, реализованные любым способом или технологией для хранения информации, такой как машиночитаемые команды, структуры данных, программные модули или другие данные.

Компьютерные носители информации включают в себя, но не в ограничительном смысле, оперативное запоминающее устройство (ОЗУ, RAM), постоянное запоминающее устройство (ПЗУ, ROM), стираемое программируемое постоянное запоминающее устройство (СППЗУ, EPROM), электрически стираемое программируемое постоянное запоминающее устройство (ЭСППЗУ, EEPROM), флэш-память или память, использующую другую технологию; постоянное запоминающее устройство на компакт-диске (CD-ROM), универсальные цифровые диски (DVD) или другой оптический дисковый накопитель; магнитные кассеты, магнитную ленту, магнитный дисковый накопитель или другие магнитные запоминающие устройства или любой другой носитель, который может быть использован для хранения необходимой информации и к которому может осуществлять доступ компьютер (100). Среда передачи данных обычно воплощает машиночитаемые команды, структуры данных, программные модули или другие данные в сигнале, модулированном данными, таком как несущая или другой механизм переноса информации, и включает в себя любые среды доставки информации. Термин «сигнал, модулированный данными» означает сигнал, одна или более характеристик которого устанавливается или изменяется таким образом, чтобы обеспечить кодирование информации в сигнале. В качестве примера, но не ограничения, среда передачи данных включает в себя проводную среду, такую как проводная сеть или прямое кабельное соединение, и беспроводную среду, такую как акустическая, радиочастотная, инфракрасная и другие беспроводные среды. Комбинации любых упомянутых выше сред также должны быть включены в диапазон машиночитаемых носителей информации.

Системная память (130) включает в себя компьютерный носитель информации в виде энергозависимой и/или энергонезависимой памяти, такой как постоянное запоминающее устройство (ПЗУ, ROM) (131) и оперативное запоминающее устройство (ОЗУ, RAM) (132). Обычно в ПЗУ (131) хранится базовая система (133) ввода/вывода (BIOS), содержащая базовые процедуры, способствующие передаче информации между элементами внутри компьютера (110), например, при запуске. ОЗУ (132) обычно содержит данные и/или программные модули, к которым можно осуществить доступ немедленно и/или которыми в текущий момент оперирует процессор (120). В качестве примера, но не ограничения, на Фиг.1 проиллюстрированы операционная система (134), прикладные программы (135), другие программные модули (136) и данные (137) программ.

Компьютер (110) также может содержать другие съемные/несъемные, энергозависимые/энергонезависимые компьютерные носители информации. Исключительно в качестве примера на Фиг.1 проиллюстрированы накопитель (141) на жестких магнитных дисках, который осуществляет считывание с несъемных энергонезависимых магнитных носителей информации или запись на них, дисковод (151) для магнитного диска, который осуществляет считывание со съемного энергонезависимого магнитного диска (152) или запись на него, и дисковод (155) для оптического диска, который осуществляет считывание со съемного энергонезависимого оптического диска (156), такого как компакт-диск CD-ROM, или других оптических носителей информации или запись на них. Другие съемные/несъемные, энергозависимые/энергонезависимые компьютерные носители информации, которые могут быть использованы в этой приводимой в качестве примера операционной среде, включают в себя, но не в ограничительном смысле, кассеты с магнитной лентой, карточки флэш-памяти, универсальные цифровые диски, цифровую видеомагнитофонную ленту, твердотельное ОЗУ, твердотельное ПЗУ и тому подобное. Накопитель (141) на жестких магнитных дисках обычно подсоединен к системной шине (121) посредством интерфейса несъемной памяти, такого как интерфейс (140), а дисковод (151) для магнитного диска и дисковод (155) для оптического диска обычно подсоединены к системной шине (121) посредством интерфейса съемной памяти, такого как интерфейс (150).

Дисководы и соответствующие им компьютерные носители информации, описанные выше и проиллюстрированные на Фиг.1, обеспечивают хранение машиночитаемых команд, структур данных, программных модулей и других данных для компьютера (110). Например, на Фиг.1 накопитель (141) на жестких магнитных дисках проиллюстрирован как хранящий операционную систему (144), прикладные программы (145), другие программные модули (146) и данные (147) программ. Следует отметить, что эти компоненты могут либо быть идентичными операционной системе (134), прикладным программам (135), другим программным модулям (136) и данным (137) программ, либо отличаться от них. Операционной системе (144), прикладным программам (145), другим программным модулям (146) и данные (147) программ даны здесь другие ссылочные позиции для того, чтобы проиллюстрировать тот факт, что, как минимум, они являются другими копиями. Пользователь может осуществлять ввод команд и информации в компьютер (110) посредством устройств ввода, таких как клавиатура (162) и координатно-указательное устройство (161), обычно именуемое мышью, шаровым манипулятором или сенсорной панелью.

В число других устройств ввода (не показанных на чертеже) могут входить джойстик, игровая панель, спутниковая антенна, сканер, радиоприемник и телевизионный приемник или приемник видеовещания или подобные им устройства. Часто эти и другие устройства ввода соединены с процессором (120) посредством проводного или беспроводного интерфейса (160) пользовательского ввода, подсоединенного к системной шине (121), но они могут быть соединены с процессором посредством другого интерфейса и других структур шины, таких, например, как параллельный порт, игровой порт, универсальная последовательная шина (USB), интерфейс стандарта IEEE 1394 (стандарт Института инженеров по электротехнике и радиоэлектронике), интерфейс Bluetooth™, беспроводный интерфейс стандарта IEEE 802.11(стандарт Института инженеров по электротехнике и радиоэлектронике) и т.д. Помимо этого, компьютер (110) может также содержать устройство ввода речи или аудиоинформации, такое как микрофон или матрица (198) микрофонов, равно как и громкоговоритель (197) или другое устройство вывода, соединенных посредством аудиоинтерфейса (199), также включающего в себя традиционные проводные или беспроводные интерфейсы, такие, например, как параллельный интерфейс, последовательный интерфейс, интерфейс USB, интерфейс IEEE 1394, интерфейс Bluetooth™ и т.д.

Также к системной шине (121) посредством интерфейса, такого как видеоинтерфейс (190), подсоединен монитор (191) или другой тип устройства отображения. В дополнение к монитору компьютеры могут также содержать другие периферийные устройства вывода, такие как принтер (196), который может быть подсоединен посредством периферийного интерфейса (195) вывода.

Компьютер (110) может функционировать в сетевой среде, используя логические соединения с одним или более удаленными компьютерами, такими как удаленный компьютер (180). Удаленный компьютер (180) может представлять собой персональный компьютер, сервер, маршрутизатор, сетевой персональный компьютер (РС), одноранговое устройство или другой узел общей сети и обычно включает в себя многие или все элементы, описанные выше в отношении компьютера (110), хотя на Фиг.1 проиллюстрировано только запоминающее устройство (181). Логические соединения, изображенные на Фиг.1, включают в себя локальную сеть (LAN) (171) и глобальную сеть (WAN) (173), но могут также включать в себя и другие сети. Такие сетевые среды часто используются в офисах, сетях масштаба предприятия, интрасетях и в сети Интернет.

При использовании в сетевой среде LAN компьютер (110) соединен с LAN (171) посредством сетевого интерфейса или адаптера (170). При использовании в сетевой среде WAN компьютер (110) обычно содержит модем (172) или другое средство для установления связи через сеть WAN (173), такую как сеть Интернет. Модем (172), который может быть внутренним или внешним, может быть подсоединен к системной шине (121) посредством интерфейса (160) пользовательского ввода или другого соответствующего механизма. В сетевой среде программные модули, изображенные в отношении компьютера (110), или их части могут храниться в удаленном запоминающем устройстве. В качестве примера, но не ограничения, Фиг.1 изображает удаленные прикладные программы (185), как размещенные на запоминающем устройстве (181). Следует понимать, что показанные сетевые соединения приводятся в качестве примера и могут быть использованы и другие средства установления линии связи между компьютерами.

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

2.0 Введение

«Средство идентификации аудиовизуальной информации» в том виде, как оно описано в данном описании, обеспечивает индивидуальным клиентам осуществляемую в реальном масштабе времени идентификацию объектов аудиовизуальной информации, включенных в поток аудиовизуальной информации, мониторинг которого осуществляется, такой как радио-, телевизионное или Интернет-вещание. Такие объекты аудиовизуальной информации могут включать в себя песни, рекламные ролики, музыкальные заставки, позывные станций и т.д.

Вообще, идентификация объектов аудиовизуальной информации обеспечивается для индивидуальных клиентов посредством сравнения сгенерированных клиентом «следов» с большой базой данных хранящихся заранее вычисленных «следов» (именуемых в данном документе «характерными отпечатками» для того, чтобы отличать их от «следов», сгенерированных клиентом) с известными идентификационными данными. Эти сгенерированные клиентом «следы» вычисляются каждым клиентом на основе образцов потока аудиовизуальной информации на постоянной основе и передаются на сервер для идентификации.

Кроме того, при условии, что имеется ограниченное количество потоков аудиовизуальной информации и гораздо большее количество клиентов, многие из этих «следов», посылаемых на сервер, вероятно, являются почти идентичными, поскольку многие из клиентов будут одновременно осуществлять мониторинг одного и того же потока аудиовизуальной информации. Это наблюдение использовано при создании пригодного к поиску динамического кэша «следов», предназначенного для ограничения количества запросов в базу данных, необходимых для идентификации конкретных «следов», а потому и для идентификации объектов аудиовизуальной информации, связанных с этими «следами». Одно из преимуществ поиска в кэше «следов», а не в базе данных, заключается в том, что работоспособная база данных «характерных отпечатков» обычно будет включать в себя миллионы элементов, в то время как кэш следов обычно будет меньше на порядки этой величины.

Кэш «следов» кэширует только одну копию свежих «следов», присланных различными клиентами, вместе с результатами поиска в базе данных как положительными, так и отрицательными. Иначе говоря, любой «след», присланный одним из клиентов, который («след») на текущий момент не существует в кэше, будет сохранен в кэше, по меньшей мере, временно, что будет более подробно объяснено ниже. Следовательно, поиск в кэше «следов» осуществляется перед тем, как сделать запрос в базу данных. База данных запрашивается для идентификации нового сгенерированного клиентом «следа» только в том случае, когда отсутствует совпадающий с ним «след» в кэше «следов». Кроме того, «следы», хранящиеся в кэше «следов», удаляются как функция времени. В одном варианте осуществления изобретения она представляет собой просто заранее установленный «срок жизни», в то время как в родственном варианте осуществления изобретения это время жизни основывается на промежутке времени, отсчитываемом после момента, когда на сервер каким-нибудь клиентом был прислан последний совпадающий «след». Иначе говоря, элементы кэша просто удаляются из кэша по мере того как они стареют, не имея обращений совпадающих с ними «следов».

Эти общие концепции проиллюстрированы на приводимой в качестве примера структурной схеме системы, которая иллюстрирует общее функциональное отношение между функциональными компонентами для реализации Средства идентификации аудиовизуальной информации. В частности, на Фиг.2 показано, что каждый из множества клиентов (200) принимает поток (210) вещания аудиовизуальной информации. Как сказано здесь при более подробном рассмотрении, совокупность доступных потоков (210) аудиовизуальной информации, таких как вещательные передачи радиостанций, телевизионные и кабельные вещательные передачи, сетевая потоковая аудиовизуальная информация и т.д., существенно меньше, чем количество потенциальных клиентов. Следовательно, мониторинг большинства потоков (210) аудиовизуальной информации будет одновременно осуществляться более чем одним клиентом (200), а потенциально сотнями, тысячами или даже миллионами клиентов. Однако следует отметить, что не все потоки (210) аудиовизуальной информации будут доступны для всех клиентов (200), поскольку потоки (210) аудиовизуальной информации включают в себя локально доступное вещание, а клиенты могут быть расположены где угодно в мире, поддерживая связь с сервером (230) через сеть Интернет (220) или другую сеть.

Затем клиенты (200) берут образцы потока (210) аудиовизуальной информации, мониторинг которого они осуществляют, и посылают вычисленные «следы» по сети или Интернету (220) на сервер (230) (или группе серверов). Сервер (230) затем проверяет кэш (240) «следов», и, если это необходимо, то и базу (250) данных «характерных отпечатков», пытаясь идентифицировать объекты аудиовизуальной информации, на основе которых были генерированы «следы». Если идентификация произведена, то идентификационная информация об аудиовизуальной информации, соответствующая конкретным следам, возвращается сервером (230) посылающему клиенту (200) по сети (220).

2.1 Обзор системы

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

После этого для каждого клиента сервер использует неточное отождествление для того, чтобы определить, совпадает ли какой-либо из «следов» с каким-либо из «характерных отпечатков» в базе данных в пределах некоторой пороговой величины или допуска. Использование таких технологий неточного отождествления является предпочтительным по сравнению с технологиями точного отождествления по той причине, что «следы», вычисленные какими-либо из различных клиентов, могут несколько различаться вследствие шума, помех, ослабления сигнала и т.д. даже в том случае, когда «следы» номинально вычислены на основе в точности тех же самых частей потока аудиовизуальной информации. Кроме того, использование неточного отождествления также учитывает небольшие временные смещения во взятых как образцы частях потока аудиовизуальной информации, на основе которых были вычислены «следы».

Всякий раз, когда «след», полученный от какого-нибудь клиента, совпадает с «характерным отпечатком» (либо в кэше «следов», либо в базе данных «характерных отпечатков»), сервер сообщает этому клиенту идентификационные данные конкретного объекта аудиовизуальной информации, соответствующего этому «следу». В случае таких объектов аудиовизуальной информации, как песни, эти идентификационные данные обычно включают в себя такую информацию, как, например, исполнитель, наименование песни, наименование альбома, жанр и т.д. Очевидно, что если объект аудиовизуальной информации известен, то с «характерными отпечатками» в базе данных, которые используются для идентификации этого объекта аудиовизуальной информации, может быть связана любая необходимая информация.

Однако вместо того, чтобы проводить требующий больших усилий поиск в базе данных «характерных отпечатков» по каждому «следу», присланному на сервер, описанное здесь Средство идентификации аудиовизуальной информации вводит дополнительный расположенный на стороне сервера кэш «следов», который использует тот факт, что в любой момент времени многие из сгенерированных пользователями «следов», вероятно, являются почти идентичными, если предположить, что имеется ограниченное количество потоков аудиовизуальной информации и что обычно в любой данный момент времени имеется большое количество пользователей, принимающих один и тот же поток аудиовизуальной информации. Иначе говоря, в любой данный момент времени вероятно, что имеется множество, потенциально десятки тысяч или даже миллионы, людей, слушающих один и тот же поток аудиовизуальной информации, такой как конкретные вещательные передачи радио-, телевизионного или Интернет-вещания. Это наблюдение позволяет создать на стороне сервера кэш, который кэширует как поступающие «следы», так и результаты поиска в базе данных совпадающих с ними «характерных отпечатков».

В частности, каждый поступающий от каждого клиента «след» сначала проверяется по кэшу «следов», который содержит в себе некоторое количество «следов». Если этот «след» в кэше «следов» отсутствует, то он здесь сохраняется, и производится поиск в полной базе данных. Результаты этого поиска в базе данных как положительные, так и отрицательные сохраняются затем в кэше «следов» наряду со «следом», присланным клиентом. Поиски как в кэше «следов», так и в базе данных могут выполняться с использованием традиционных технологий, таких как, например, линейный перебор (то есть, последовательно) с наложением ограничений (известный способ ускорения сравнений отклонений с использованием линейного перебора).

В другом варианте осуществления изобретения поиски в базе данных ускорены за счет использования битового векторного индексирования, как это описано в заявке на патент США, которая находится на рассмотрении одновременно с данной заявкой, озаглавлена «Multidimensional Data Object Searching Using Bit Vector Indices» («Поиск объектов многомерных данных с использованием битовых векторных индексов»), имеет дату подачи 23 июня 2003 года и присвоенный ей порядковый номер 10/602,438, и содержание которой включено в настоящее описание посредством этой ссылки. Этот подход, заключающийся в битовом векторном индексировании, также описан в публикации, которая озаглавлена «Indexing High Dimensional Rectangles for Fast Multimedia Identification» («Индексирование многомерных прямоугольников для быстрой идентификации мультимедиа»), имеет своими авторами Джона К. Платта (John C. Platt) и Кристофера Дж. К. Берджеса (Christopher J. C. Burges), опубликована в Microsoft Technical Report (Технический отчет компании «Microsoft») MSR-TR-2003-38, датированном 28 октября 2003 г., и содержание которой включено в настоящее описание посредством ссылки.

Вообще, способы битового векторного индексирования, описанные в вышеупомянутых заявке на патент США и соответствующем Техническом отчете компании «Microsoft», рассматривают проблему быстрого осуществления точечных запросов в отношении многомерных областей. Такие запросы полезны при решении становящихся все более важными задач идентификации и поиска мультимедиа, в которых различные элементы базы данных имеют различные показатели сходства. В противоположность обычному индексированию в базе данных, которое сосредоточено на индексировании для многомерных запросов о ближайшем соседнем элементе и эпсилон-интервале, индексирование для точечных запросов в отношении многомерных областей, предоставляет эффективный способ индексирования, в котором для достижения значительных выигрышей в производительности сделана ставка на сочетание избыточности и битового векторного индексирования. Было отмечено, что такие способы обеспечивают значительное повышение производительности по сравнению с характерными для реального мира способами линейного перебора.

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

2.2 Обзор конфигурации системы

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

Вообще, Средство идентификации аудиовизуальной информации начинает свою работу в отношении каждого клиента (200) при приеме каждым клиентом одного из потоков (210) аудиовизуальной информации с использованием для приема потока аудиовизуальной информации модуля (305) захвата потока аудиовизуальной информации. Следует отметить, что потоки (210) аудиовизуальной информации могут представлять собой потоки аудиоинформации, потоки видеоинформации или смесь обоих видов потоков. После этого клиент (200) производит взятие образцов поступающих потоков аудиовизуальной информации в реальном масштабе времени, используя для этого модуль взятия образцов потоков аудиовизуальной информации. После этого каждым клиентом используется модуль (315) вычисления «следов» для непрерывной генерации «следов» на основе потоков аудиовизуальной информации, подвергаемых взятию образцов. Отметим, что количество и частота «следов», генерируемых каждым клиентом, описывается более подробно ниже, в Разделе 3. Сгенерированные «следы» затем предоставляются модулю (320) передачи «следов», который передает «следы» на сервер (230) через сеть или Интернет (220).

После этого сервер (230) использует модуль приема «следов» для приема переданных «следов» от различных клиентов (200). Как только сервер (230) начинает принимать «следы» от различных клиентов (200), они предоставляются модулю (335) поиска следов, который сначала производит поиск в кэше (240) «следов» для обнаружения совпадающих «следов». Если совпадающий «след» в кэше «следов» отсутствует, то данный «след» сохраняется в кэше «следов», и модулем (335) поиска следов выполняется поиск в базе (250) данных «характерных отпечатков».

Наконец, модуль (345) поддержания кэша обеспечивает операции общей очистки кэша. В частности, как было отмечено выше, все «следы», принятые сервером (230), которые не могут быть найдены в кэше (240) «следов», добавляются в кэш, наряду с результатами соответствующего поиска в базе данных (как положительными, так и отрицательными). Однако без наложения некоторых ограничений на этот процесс, кэш (240) «следов» быстро бы переполнился. Поэтому, как будет более подробно описано в разделе 3, производится очистка кэша «следов» от более старых «следов» как функция времени. Более конкретно, в одном варианте осуществления изобретения модуль (345) поддержания кэша удаляет из кэша любые «следы» старше, чем некоторый заранее заданный промежуток времени. В качестве альтернативы, модуль (345) поддержания кэша удаляет любые «следы», которые не были отождествлены модулем (335) поиска следов с поступающими «следами» в течение некоторого заранее заданного промежутка времени. В других дополнительных вариантах осуществления изобретения модуль (345) поддержания кэша использует либо комбинацию этих сроков жизни «следов», либо различные сроки жизни для «следов» с положительными ответами из базы данных (250) и отрицательными ответами из базы данных.

3.0 Обзор функционирования

Вышеописанные программные модули используются для реализации Средства идентификации аудиовизуальной информации. Как было в обобщенном виде указано выше, Средство идентификации аудиовизуальной информации обеспечивает индивидуальным клиентам осуществляемую в реальном масштабе времени идентификацию объектов аудиовизуальной информации, включенных в поток аудиовизуальной информации, мониторинг которого осуществляется, такой как радио- или Интернет-вещание. Нижеследующие разделы предлагают подробное рассмотрение функционирования Средства идентификации аудиовизуальной информации и подробное рассмотрение приводимых в качестве примеров способов для реализации программных модулей, описанных в разделе 2 в отношении Фиг.2 и Фиг.3. Помимо этого, следуя подробному описанию функционирования Средства идентификации аудиовизуальной информации, приводимому ниже в разделе 3.1, со ссылкой на Фиг.4 представлена блок-схема последовательности операций, которая обобщает общее функционирование Средства идентификации аудиовизуальной информации, рассматриваемого в данном подробном описании.

3.1 Подробности функционирования Средства идентификации аудиовизуальной информации

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

3.1.1 Вычисление «следов» и составление базы данных «характерных отпечатков»

Вычисление «следов» или «характерных отпечатков» на основе аудиосигнала или на основе образцов потока аудиоданных для использования при идентификации аудиовизуальной информации представляет собой концепцию, хорошо знакомую специалистам в данной области техники. Вообще, такие системы часто функционируют таким образом, что берут образец поступающего потока аудиовизуальной информации и вычисляют компактные векторы-признаки (то есть, «следы») на основе этого взятого в качестве образца сигнала. Эти компактные векторы-признаки могут содержать векторы малой размерности или они могут содержать двоичные хэш-ключи. Поскольку вычисление «следов» на основе взятых в качестве образцов потоков аудиовизуальной информации известно специалистам в данной области техники, эта тема не будет рассматриваться здесь подробно.

Что касается Средства идентификации аудиовизуальной информации, то в нем вычисление «следов» на основе потока аудиовизуальной информации выполняется с использованием любой из ряда традиционных технологий. Например, одна из технологий вычисления «следов», использованная в протестированном варианте осуществления Средства идентификации аудиовизуальной информации, описана в публикации заявки на патент США, имеющей номер US 2003/0236661 и озаглавленной «System and Method for Noise-Robust Feature Extraction» («Система и способ для шумоустойчивого выделения признака»), содержание которой включено в настоящее описание посредством ссылки.

Система, описанная в вышеупомянутой публикации заявки на патент США, имеющей номер US 2003/0236661, обычно функционирует таким образом, что вычисляет или выделяет признаки из аудиосигналов, используя для этого «выделитель признаков», который обучается на смеси искусственных и/или реальных сигналов с использованием способа «Распознающего искажения анализа» (DDA) для определения параметров выделителя признаков. Описываемый выделитель признаков берет сигнал, имеющий одно или более измерений с временной или пространственной структурой, применяет ориентированный анализ основных компонентов (OPCA) к ограниченным областям сигнала, агрегирует выход множественных результатов ОРСА, которые примыкают друг к другу в пространстве или во времени и применяют ОРСА к агрегату. Этапы агрегирования примыкающих выходных значений ОРСА и применение ОРСА к агрегированным значениям выполняется один или более раз для выделения шумоустойчивых имеющих малую размерность признаков из сигналов, включающих в себя аудиосигналы, изображения, видеоданные или любой другой сигнал временной или частотной области. Будучи один раз обучен, выделитель признаков затем просто используется для генерирования «следов» («характерных отпечатков»), используемых описываемым здесь Средством идентификации аудиовизуальной информации.

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

«Характерные отпечатки», составляющие базу данных «характерных отпечатков», обычно вычисляются тем же способом, что и следы, с использованием тех же самых алгоритмов таким образом, чтобы имелось четкое соответствие между «следами», вычисленными каждым клиентом, и «характерными отпечатками», используемыми для заполнения базы данных «характерных отпечатков». Однако в отличие от «следов», которые вычисляются непрерывно по мере поступления потока аудиовизуальной информации, «характерные отпечатки» вычисляются только один раз на основе одного или более образцов, взятых из конкретных мест в пределах известных объектов аудиовизуальной информации, так, чтобы заполнить хранимые в базе данных «характерные отпечатки», соответствующие этим известным объектам аудиовизуальной информации. Количество «характерных отпечатков», вычисленных для каждого объекта аудиовизуальной информации, может быть настолько малым или настолько большим, насколько это необходимо. Однако в протестированном варианте осуществления изобретения было замечено, что предоставления нескольких «характерных отпечатков» на один объект аудиовизуальной информации было достаточно для того, чтобы обеспечить устойчивую идентификацию объекта аудиовизуальной информации.

Будучи один раз созданной, база данных «характерных отпечатков» затем просто является объектом доступа со стороны сервера, согласно с приведенным здесь описанием, без необходимости повторного вычисления «характерных отпечатков» для известных объектов аудиовизуальной информации. Однако база данных известных «характерных отпечатков» может впоследствии обновляться с внесением в нее новых «характерных отпечатков» по мере того, как создаются новые объекты аудиовизуальной информации (песни и т.д.). По этой причине предпочтительно, чтобы база данных известных «характерных отпечатков» создавалась в автономном режиме с использованием каких бы то ни было алгоритмов вычисления «следов», подлежащих использованию клиентами для вычисления следов, и после этого просто предоставлялась серверу, так чтобы устранить любую дополнительную вычислительную нагрузку на сервер во время операций идентификации аудиовизуальной информации, исполняемых описанным здесь Средством идентификации аудиовизуальной информации.

3.1.2 Время существования «следов» в кэше

Одно из преимуществ расположенного на стороне сервера кэша «следов», предусмотренного Средством идентификации аудиовизуальной информации, заключается в том, что размер кэша относительно мал, что делает поиски в кэше чрезвычайно быстрыми. В частности размер кэша является функцией максимальной ожидаемой задержки между запросами от каждого клиента и количества уникальных потоков аудиовизуальной информации, для которых предоставляются услуги по идентификации. Кроме того, следует отметить, что размер кэша не является функцией количества индивидуальных клиентов или пользователей, которые осуществляют доступ к серверу с запросами об идентификации «следов».

В частности, каждый конкретный поток вещания аудиовизуальной информации приблизительно синхронизирован по каждому клиенту, который принимает этот конкретный поток аудиовизуальной информации. Например, любые два или более клиентов, принимающих одну и ту же радиостанцию, вероятно, принимают один и тот же сигнал в пределах очень небольшого максимального временного смещения, длительностью примерно около одной секунды или около того, что зависит от типа и источника принимаемого потока аудиовизуальной информации. То же самое верно также и для большинства вещательных передач потоковой аудиовизуальной информации Интернет- или сетевого вещания.

По этой причине нет необходимости держать «следы» в кэше аудиовизуальной информации в течение промежутка времени, превышающего некоторое малое кратное максимального ожидаемого времени задержки между клиентами (причем, время задержки также включает в себя максимальную ожидаемую задержку по каждому клиенту на вычисление и передачу «следа» на сервер). Иначе говоря, эта задержка представляет собой просто максимальное значение времени между приемом сервером первого «следа» для данной части конкретного объекта аудиовизуальной информации и приемом сервером последнего «следа» (от самого медленного клиента) для этой части того же самого объекта аудиовизуальной информации. Следовательно, следы необходимо держать в кэше только в течение короткого промежутка времени длительностью примерно несколько секунд. В результате отсутствует необходимость в большом кэше для хранения всех уникальных поступающих на сервер «следов».

В родственном варианте осуществления изобретения, вместо попыток определить или оценить максимальные значения времени задержки для установления времени существования (сроков жизни) «следов» в кэше, предлагается более простое решение, которое заключается в том, чтобы просто удалять «следы» из кэша после того, как они не совпали ни с какими поступающими «следами» в течение некоторого короткого промежутка времени длительностью примерно в одну секунду или около того. В дополнительных альтернативных вариантах осуществления изобретения также могут быть использованы другие схемы кэширования, включая, например, использование фиксированного размера кэша, который удаляет «следы» основываясь на традиционной логике удаления элементов с наиболее давним использованием.

3.1.3 Поиск в кэше «следов»

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

Определение того, совпадают ли поступающие «следы» с какими-либо «следами» в кэше «следов», производится с использованием традиционных технологий сравнения сигналов. Такие технологии включают в себя, например, традиционную взаимную корреляцию и способы линейного перебора, которые непосредственно сравнивают точки на поступающем «следе» с каждым из «следов» в кэше «следов». В любом случае, предпочтительно, чтобы, как было отмечено выше, отождествление было неточным, поскольку «следы», вычисленные какими-либо из различных клиентов, могут различаться вследствие шума, помех, ослабления сигнала и т.д. даже в том случае, когда номинально «следы» вычислены на основе тех же самых частей потока аудиовизуальной информации. Точное отождествление может использоваться, но оно оказалось менее эффективным в том, что касается правильной идентификации совпадающих «следов». В одном варианте осуществления изобретения неточное отождествление использует для повышения точности перенормализации по «характерному отпечатку», что хорошо известно в данной области техники и, например, описано в публикации, озаглавленной «Distortion Discriminant Analysis for Audio Fingerprinting» («Распознающий искажения анализ для снятия «характерных отпечатков»»), которая имеет своими авторами: Кристофера Дж. К. Берджеса (Christopher J. C. Burges), Джона К. Платта (John C. Platt), Соумя Джана (Soumya Jana), опубликована в IEEE Transactions on Speech and Audio Processing (Трудах Института инженеров по электротехнике и радиоэлектронике, раздел «Обработка речи и аудиоинформации»), а именно IEEE Transactions on Speech and Audio Processing, Том 11, № 3, страницы 165 - 174, май 2003 г., и содержание которой включено в настоящее описание посредством этой ссылки.

В случае неточного отождествления совпадение определяется относительно некоторого показателя отклонения f и соответствующее пороговое значение θ. Например, если «следы» представляют собой векторы малой размерности, то при прямом сравнении поступающего «следа» Х со множеством кэшированных «следов» Y один простой способ провести сравнение следов заключается в том, чтобы просто оценить квадрат Евклидова расстояния в уравнении 1 один раз для каждого следа, проиндексированного индексом j:

(Уравнение 1)

где x _i представляет собой i-й элемент «следа», y _ij представляет собой i-й элемент j-го кэшированного «следа», n представляет собой количество компонентов вектора «следа», а θ _j представляет собой пороговое значение отклонения, связанного с j-м кэшированным «следом».

Следует отметить, что способ сравнения, описанный выше, является лишь одним из очень большого количества традиционных технологий для сравнения сигналов или следов. Такие способы хорошо известны специалистам в данной области техники и не будут здесь описываться. Однако следует понимать, что для использования с описанным здесь Средством идентификации аудиовизуальной информации пригодна любая традиционная технология, предназначенная для сравнения двух сигналов или следов, и что не подразумевается, чтобы Средство идентификации аудиовизуальной информации было ограничено использованием простого линейного перебора, описанного выше. Кроме того, имеется также ряд традиционных технологий для ускорения поисков, проводимых с целью отождествления сигналов или «следов». Один простой способ заключается в том, чтобы просто проводить поиск в кэше в порядке частоты появления предыдущих совпадений. Очевидно, что имеются и другие традиционные схемы ускорения поиска, любые из которых пригодны для использования с описанным здесь Средством идентификации аудиовизуальной информации.

3.1.4 Поиски в базах данных

Как было отмечено выше, поиски в базе данных производятся только в том случае, если конкретный поступающий «след» не совпадает ни с каким из «следов» в кэше «следов». Фактически осуществляемый поиск в базе данных «характерных отпечатков» выполняется во многом таким же образом, как и поиск совпадений в кэше «следов». На самом деле, для сравнения поступающих «следов» с «характерными отпечатками», содержащимися в базе данных «характерных отпечатков», используются те же самые типы сравнений «следов», что и описанные выше в отношении поисков в кэше «следов». Однако следует отметить, что, как ожидается, база данных «характерных отпечатков» будет существенно больше, чем кэш «следов». На самом деле, можно ожидать, что база данных объектов аудиовизуальной информации, содержащая только «характерные отпечатки» песен, легко может насчитывать миллионы элементов в случае, если она должна в полной мере представлять имеющийся в наличие спектр музыкальных произведений, потоковая передача или вещание которых осуществляется по всему миру. Следовательно, способы ускорения поиска в базе данных имеют тенденцию стать существенно более важными, чем ускорение поиска в кэше «следов».

В этом отношении осуществление поиска в порядке популярности или частоты появления обещает дать значительное увеличение производительности, поскольку существенно более вероятно, что передаваться потоком в одном или более потоках аудиовизуальной информации будет очень популярная песня, а не некоторая устаревшая песня неизвестного исполнителя. Измерение частоты появления представляет собой легко выполнимую задачу. В частности один простой метод заключается в том, чтобы просто считать количество раз, которое конкретный объект аудиовизуальной информации был идентифицирован в различных потоках и в различные моменты времени на протяжении некоторого периода времени (посредством подсчета ответов из кэша «следов» и совпадений с базой данных). Затем, для целей поиска элементы в базе данных «характерных отпечатков» могут быть упорядочены в порядке частоты появления. Кроме того, как было отмечено выше, имеется ряд традиционных технологий для ускорения поисков совпадающих сигналов или «следов» в базе данных, и любые из этих технологий пригодны для использования с описанным здесь Средством идентификации аудиовизуальной информации.

3.1.5 Поиски в локальных базах данных

В одном варианте осуществления изобретения нагрузка на сервер еще более уменьшена за счет автоматической загрузки некоторой небольшой части или подмножества общей базы данных «характерных отпечатков» (и, возможно, вдобавок к этому, некоторой части кэша «следов») одному или более локально расположенным клиентам. Обычно, «следы» и/или «характерные отпечатки», которые загружаются индивидуальным клиентам, должны быть теми, что наблюдаются наиболее часто (то есть, теми «следами»/«характерными отпечатками», которые соответствуют наиболее популярным объектам аудиовизуальной информации).

В этом варианте осуществления изобретения вместо того, чтобы сразу посылать каждый вычисленный «след» на сервер, каждый клиент, имеющий подмножество базы данных «характерных отпечатков» и/или кэша «следов» (то есть, «локальное подмножество «следов»»), будет сначала запрашивать локальное подмножество «следов» прежде, чем посылать какие-либо вычисленные «следы» на сервер в целях идентификации. Если какой-либо вычисленный «след» совпадает с каким-либо из «следов» в локальном подмножестве «следов», то вычисленному «следу» присваивается любая идентификационная информация, связанная с совпадающим «следом» в локальном подмножестве «следов», и вычисленный «след» затем не посылается на сервер. Таким образом, по меньшей мере, некоторая нагрузка по идентификации аудиовизуальной информации может быть переложена с сервера на одного или более локальных клиентов.

Следует отметить, что «следы» в локальном подмножестве «следов» могут содержать много больше «характерных отпечатков» на одну песню, чем те, что находятся в полной базе данных на сервере, поскольку количество популярных в текущий момент объектов аудиовизуальной информации, таких как песни, относительно мало по сравнению с полной совокупностью объектов аудиовизуальной информации. Это имеет дополнительное преимущество дальнейшего снижения количества «следов», посылаемых на сервер, поскольку, как только совпадение установлено, воспроизводимый в текущий момент объект аудиовизуальной информации может проверяться локально по локальному хранилищу «характерных отпечатков» для этого объекта аудиовизуальной информации все время, пока объект аудиовизуальной информации воспроизводится. Например, если бы «характерные отпечатки» вычислялись для песни каждые 5 секунд, то клиент не должен был бы посылать никаких «следов» на сервер все время, пока он находит ожидаемое совпадение каждые 5 секунд.

В дополнительном варианте осуществления изобретения клиент, как только идентифицировано положительное совпадение, просто прекращает посылать «следы» на сервер в течение продолжительности оставшейся части идентифицированного объекта аудиовизуальной информации, такого как песня S. Эта информация о продолжительности могла бы быть прислана клиенту с сервера вместе с другой идентификационной информацией при обнаружении положительного совпадения. Хотя это и является простым способом дополнительно уменьшить бремя нагрузки на систему сервер/кэш, он может дать ложный отрицательный результат (то есть, объект аудиовизуальной информации, который должен был бы быть идентифицирован, но который не был идентифицирован) в случае, если пользователь, например, переключает потоки аудиовизуальной информации до окончания вышеупомянутой идентифицированной песни S. Однако это можно предотвратить, если просто следить за тем, когда клиент производит переключения потоков, и при этом всякий раз, когда происходит переключение потока, немедленно начинать снова посылать «следы» на сервер (проверив их сначала по локальному подмножеству «следов», если таковое существует).

3.1.6 Идентификация объекта аудиовизуальной информации

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

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

3.2 Функционирование Средства идентификации аудиовизуальной информации

Процессы, описанные выше в отношении Фиг.2 и Фиг.3, проиллюстрированы на общей блок-схеме последовательности операций, показанной на Фиг.4. Вообще, на Фиг.4 проиллюстрирована приводимая в качестве примера блок-схема последовательности операций, показывающая несколько операционных вариантов осуществления Средства идентификации аудиовизуальной информации. Следует отметить, что любые блоки и взаимосвязи между блоками, представленные на Фиг.4 пунктирной или штрихпунктирной линиями, представляют альтернативные варианты осуществления описанного здесь Средства идентификации аудиовизуальной информации, и что любые или все эти альтернативные варианты осуществления, как будет сказано ниже, могут быть использованы в сочетании с другими альтернативными вариантами осуществления, которые описаны в разных местах по всему этому документу. Кроме того, следует отметить, что в обсуждении, приводимом ниже, система, в общем, описана в отношении единственного клиента, работающего с единственным сервером. Однако, с учетом сказанного ранее, следует отметить, что описанное здесь Средство идентификации аудиовизуальной информации в полной мере способно работать с чрезвычайно большим количеством клиентов и любым необходимым количеством серверов.

В частности, как проиллюстрировано на Фиг.4, функционирование Средства идентификации аудиовизуальной информации начинается с захвата (этап 405) клиентом (200) потока (210) аудиовизуальной информации. Захват потока аудиовизуальной информации выполняется с использованием традиционных способов, включая, например, простую настройку на радио- или телевизионное вещание, или подписку на вещание потоковой аудиовизуальной информации или одновременное вещание через сеть, такую как сеть Интернет. Когда поток (210) аудиовизуальной информации захвачен (этап 405), клиент на основе образцов потока аудиовизуальной информации генерирует имеющие реальный масштаб времени «следы» (этап 410). Эти имеющие реальный масштаб времени «следы» аудиовизуальной информации затем передаются (этап 415) на сервер (230) с использованием традиционных протоколов сетевой передачи. Вычисление и передача «следов» аудиовизуальной информации продолжается все время, пока принимается поток аудиовизуальной информации, и все время, пока клиент желает иметь идентификационную информацию для объектов аудиовизуальной информации, включенных в поток аудиовизуальной информации.

Однако, как было отмечено выше, в одном варианте осуществления изобретения клиент будет временно приостанавливать вычисление и передачу «следов» на сервер вслед за приемом с сервера идентификационной информации об объекте аудиовизуальной информации. Например, как было отмечено выше, «характерные отпечатки», вычисляемые для базы данных «характерных отпечатков», вычисляются на основе известных мест в известных объектах аудиовизуальной информации. Следовательно, остающаяся длительность или продолжительность этих объектов аудиовизуальной информации будет известна относительно вычисленного «следа» (за вычетом времени задержки от посылки «следа» на сервер и приема с сервера идентификационных данных об объекте аудиовизуальной информации). Вследствие этого, согласно данному варианту осуществления изобретения, при условии, что эта информация о продолжительности предоставлена вместе с идентификационной информацией об объекте аудиовизуальной информации, у клиента не будет необходимости ни вычислять, ни посылать на сервер никакие дополнительные «следы» до момента после конечной точки объекта аудиовизуальной информации, воспроизводимого в текущий момент. Однако в случае, если клиент начинает захват другого потока аудиовизуальной информации (как, например, при переключении с одной радиостанции на другую), то вычисление и передача «следов» немедленно возобновятся. Должно быть ясно, что этот вариант осуществления изобретения может существенно уменьшить нагрузку на сервер, значительно сократив количество «следов», посылаемых на сервер после возвращения клиенту данных успешной идентификации объекта аудиовизуальной информации.

После того, как сервер (230) принимает (этап 420) от клиентов (200) переданные ими «следы», сервер немедленно проверяет кэш (240) «следов», чтобы определить (этап 430), имеется ли в кэше совпадающий «след». Если совпадающий «след» в кэше «следов» имеется, то совпадающий «след» в кэше проверяется (этап 435), чтобы определить, связан ли он с положительным ответом из базы данных. Если совпадающий «след» связан с положительным ответом из базы данных, то идентификационная информация об объекте аудиовизуальной информации, связанная с этим совпадающим «следом», немедленно передается (этап 460) назад клиенту (200).

Наоборот, в случае, если кэш (240) «следов» не содержит совпадающий «след», то на следующем этапе проверяют (этап 440) базу (250) данных «характерных отпечатков», пытаясь обнаружить совпадающий «след». Если совпадение в базе данных имеется (этап 445), то «след» сохраняется (этап 450) в кэше (240) «следов», и идентификационная информация об объекте аудиовизуальной информации, связанная с этим совпадающим «следом», немедленно передается (этап 460) назад клиенту (200). В случае если совпадения в базе данных нет (этап 445), то «след» и в этом случае сохраняется (этап 450) в кэше (240) «следов» как отрицательный ответ.

В любом случае, после того, как либо совпадение (на этапе 430) было или не было найдено в кэше (240) «следов», либо совпадение (на этапе 445) было или не было обнаружено в базе данных и любая связанная идентификационная информация об объекте аудиовизуальной информации передана клиенту, сервер затем просто ждет присылки от клиента следующего «следа» для сравнения его со «следами» и/или «характерными отпечатками» в кэше (240) «следов» и/или базе (250) данных «характерных отпечатков», соответственно. Кроме того, как было отмечено выше, кэш (240) «следов» управляется (этап 455) на постоянной основе таким образом, чтобы удалять элементы-«следы», сроки жизни которых истекли.

После того, как клиент (200) принимает любую идентификационную информацию об объекте аудиовизуальной информации, эта идентификационная информация обрабатывается (этап 465) клиентом и предоставляется пользователю в необходимом ему виде. Например, в одном варианте осуществления изобретения идентификационная информация об объекте аудиовизуальной информации используется для того, чтобы обеспечивать отображение для пользователя идентификационных данных текущего объекта аудиовизуальной информации по мере того, как принимается и воспроизводится поток аудиовизуальной информации. В качестве альтернативы, идентификационная информация об объекте аудиовизуальной информации может быть использована в других целях, включая, но не в смысле ограничения, формирование списков воспроизведения, составление характеристики потока аудиовизуальной информации, статистический анализ потока аудиовизуальной информации и т.д.

Наконец, в другом варианте осуществления изобретения клиентом (200) из сервера (230) загружается (этап 470) подмножество базы (250) данных «характерных отпечатков» (и/или кэша (240) «следов») для выполнения функции локальной базы данных «характерных отпечатков». Как было отмечено выше, это подмножество может также содержать дополнительные «характерные отпечатки», которые сам сервер для поиска не использует, для того, чтобы увеличить охват, что было описано выше (например, клиент может проверять несколько «характерных отпечатков» на одну песню).

В частности для относительно более популярных (или более часто наблюдаемых) объектов аудиовизуальной информации дополнительные «характерные отпечатки» вычисляются для каждого объекта аудиовизуальной информации сервером и включаются в состав подмножества «характерных отпечатков», загружаемых клиентам, для дальнейшего сокращения количества обращений на сервер. Как было описано выше, клиент в таком случае осуществляет поиск (этап 475) в этой локальной базе данных перед тем, как передать (этап 415) любые «следы» на сервер (230). В случае если при этом поиске в локальной базе данных обнаружено совпадение «следа», то соответствующий «след» не посылается на сервер (230) для обработки, как об этом и было сказано выше.

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

1. Способ обеспечения идентификации объектов аудиовизуальной информации, включенных в потоки вещания аудиовизуальной информации, мониторинг которых осуществляется клиентами, для каждого из множества компьютеров-клиентов, причем способ включает в себя использование вычислительного устройства для выполнения этапов, на которых:
по каждому из множества компьютеров-клиентов передают на постоянной основе сгенерированные клиентом «следы» потока аудиовизуальной информации;
для каждого переданного «следа» потока аудиовизуальной информации, который был принят сервером, используют сервер для поиска в кэше «следов» совпадающего «следа» для этого «следа» потока аудиовизуальной информации;
причем каждый «след» в кэше «следов» содержит заранее заданное время существования, и при этом любой «след», время существования которого истекло, удаляется из кэша «следов» вместе с любой связанной с ним идентификационной информацией об объекте аудиовизуальной информации;
в случае если кэш «следов» содержит совпадающий «след», передают из сервера соответствующему клиенту любую идентификационную информацию об объекте аудиовизуальной информации, связанную с этим совпадающим «следом»;
в случае если кэш «следов» не содержит совпадающий «след», осуществляют поиск в базе данных «характерных отпечатков» для того, чтобы определить, имеются ли в ней какие-либо совпадающие «характерные отпечатки» для «следа» потока аудиовизуальной информации, и сохраняют переданный «след» потока аудиовизуальной информации в кэше «следов» вместе с результатами поиска в базе данных; и
в случае если база данных «характерных отпечатков» содержит совпадающий «характерный отпечаток», передают из сервера соответствующему клиенту идентификационную информацию об объекте аудиовизуальной информации, связанную с этим «характерным отпечатком».

2. Способ по п.1, в котором генерируемые клиентом «следы» потока аудиовизуальной информации вычисляются и передаются каждым клиентом примерно около шести раз в секунду на основе образцов потока вещания аудиовизуальной информации, имеющих продолжительность примерно около шести секунд.

3. Способ по п.1, в котором заранее заданное время существования дольше для «следов», имеющих связанную с ними идентификационную информацию об объекте аудиовизуальной информации, чем для «следов», не имеющих связанной с ними идентификационной информации об объекте аудиовизуальной информации.

4. Способ по п.1, в котором время, остающееся в заранее заданном времени существования для «следа» в кэше «следов», возвращается в исходное состояние к заранее заданному времени существования, в случае, когда этот «след» в кэше «следов» совпадает со «следом» потока аудиовизуальной информации.

5. Способ по п.1, в котором «следы» в кэше «следов», которые часто совпадают со «следами» потоков аудиовизуальной информации, постоянно поддерживаются в кэше «следов» независимо от заранее заданного времени существования.

6. Способ по п.1, в котором каждый «след» в кэше «следов» удаляется из кэша «следов» вместе с любой связанной с ним идентификационной информацией об объекте аудиовизуальной информации после того, как в течение заранее заданного промежутка времени он не совпал ни с какими переданными «следами» потоков аудиовизуальной информации.

7. Способ по п.1, в котором кэш «следов» имеет фиксированный размер, и в котором всякий раз, когда в кэше «следов» сохраняется переданный «след» потока аудиовизуальной информации, из кэша «следов» удаляется самый старый в кэше «следов» «след» вместе с любой связанной с ним идентификационной информацией об объекте аудиовизуальной информации.

8. Способ по п.1, который также включает в себя этап, на котором из сервера в один или более компьютеров-клиентов загружают подмножество, состоящее из одного или более «характерных отпечатков» из базы данных «характерных отпечатков» и ноля или более «следов» из кэша «следов» и любой связанной с загруженными «характерными отпечатками» и «следами» идентификационной информации об объектах аудиовизуальной информации.

9. Способ по п.8, в котором «характерные отпечатки», присылаемые клиенту, хотя и хранятся на сервере, не используются самим сервером для отождествления следов.

10. Способ по п.8, в котором в подмножестве «характерных отпечатков» и «следов», размещенном на каждом клиенте, осуществляется поиск совпадения с каждым «следом» потока аудиовизуальной информации, сгенерированным соответствующим клиентом, перед передачей сгенерированных клиентом «следов» потока аудиовизуальной информации на компьютер-сервер, и в котором сгенерированные клиентом «следы» потока аудиовизуальной информации не посылаются на компьютер-сервер в случае, если эти сгенерированные клиентом «следы» потока аудиовизуальной информации совпадают с какими-либо элементами этого подмножества, являющимися «характерными отпечатками» и «следами».

11. Способ по п.1, в котором идентификационная информация об объекте аудиовизуальной информации, переданная каждому соответствующему клиенту, содержит остающуюся продолжительность передаваемого в текущий момент потоковым способом объекта аудиовизуальной информации, включенного в поток вещания аудиовизуальной информации,
мониторинг которого осуществляет клиент, и в котором любой клиент, принимающий такую информацию, временно приостанавливает передачу сгенерированных клиентом «следов» потока аудиовизуальной информации на сервер на время остающейся продолжительности объекта аудиовизуальной информации, передаваемого в текущий момент потоковым способом.

12. Способ по п.11, в котором передача сгенерированных клиентом «следов» потока аудиовизуальной информации на сервер возобновляется, как только система обнаруживает, что пользователь переключился на другой поток.

13. Система для обеспечения идентификации объектов аудиовизуальной информации, включенных в потоки вещания аудиовизуальной информации, для каждого из множества клиентов, включающая в себя:
средства для мониторинга любой одной из множества вещательных передач аудиовизуальной информации на каждом из множества компьютеров-клиентов;
средства для генерирования имеющих реальный масштаб времени «следов» на каждом из компьютеров-клиентов на основе образцов вещательных передач аудиовизуальной информации, мониторинг которых осуществляется;
средства для передачи каждого имеющего реальный масштаб времени «следа» от каждого компьютера-клиента группе, состоящей из одного или более компьютеров-серверов;
средства для использования для каждого имеющего реальный масштаб времени «следа», принятого группой серверов, этой группы серверов для поиска в базирующемся на сервере кэше «следов» совпадения с этим имеющим реальный масштаб времени «следом», и передачу из кэша «следов» соответствующему клиенту любой связанной с совпадающим «следом» идентификационной информации об объекте аудиовизуальной информации;
причем каждый «след» в кэше «следов» содержит заранее заданное время существования, и при этом любой «след», время существования которого истекло, удаляется из кэша «следов» вместе с любой связанной с ним идентификационной информацией об объекте аудиовизуальной информации;
средства для использования, в случае, если кэш «следов» не содержит совпадения с этим имеющим реальный масштаб времени «следом», группы серверов для поиска в базирующейся на сервере базе данных «характерных отпечатков» совпадения «характерного отпечатка» с этим имеющим реальный масштаб времени «следом», передачу из базы данных «характерных отпечатков» соответствующему клиенту любой связанной с совпадающим «характерным отпечатком» идентификационной информации об объекте аудиовизуальной информации и сохранение этого имеющего реальный масштаб времени «следа» в кэше «следов» вместе с результатами поиска в базе данных.

14. Система по п.13, в которой заранее заданное время существования дольше для «следов», имеющих связанную с ними идентификационную информацию об объекте аудиовизуальной информации, чем для «следов», не имеющих связанной с ними идентификационной информации об объекте аудиовизуальной информации.

15. Система по п.13, в которой время, остающееся в заранее заданном времени существования для «следа» в кэше «следов», возвращается в исходное состояние, в случае, когда этот «след» в кэше «следов» совпадает со «следом» потока аудиовизуальной информации.

16. Система по п.13, в которой «следы» в кэше «следов», которые часто совпадают со «следами» потоков аудиовизуальной информации, постоянно поддерживаются в кэше «следов» независимо от заранее заданного времени существования.

17. Система по п.13, в которой каждый «след» в кэше «следов» удаляется из кэша «следов» вместе с любой связанной с ним идентификационной информацией об объекте аудиовизуальной информации после того, как в течение заранее заданного промежутка времени он не совпал ни с какими переданными «следами» потоков аудиовизуальной информации.

18. Система по п.13, в которой идентификационная информация об объекте аудиовизуальной информации, переданная каждому соответствующему клиенту, содержит остающуюся продолжительность передаваемого в текущий момент потоковым способом объекта аудиовизуальной информации, включенного в поток вещания аудиовизуальной информации, мониторинг которого осуществляет клиент, и в которой любой клиент, принимающий такую информацию, временно приостанавливает передачу имеющих реальный масштаб времени «следов» группе серверов на время остающейся продолжительности передаваемого в текущий момент потоковым способом объекта аудиовизуальной информации.

19. Машиночитаемый носитель информации с машиноисполняемыми командами для обеспечения идентификации объектов аудиовизуальной информации для множества компьютеров-клиентов, причем машиноисполняемые команды включают в себя:
использование множества компьютеров-клиентов для генерирования последовательных имеющих реальный масштаб времени «следов» на основе образцов захваченных потоков аудиовизуальной информации, мониторинг которых осуществляется каждым клиентом;
передачу сгенерированных «следов» компьютеру-серверу; и
использование, для каждого переданного «следа», этого компьютера-сервера для того, чтобы:
осуществлять поиск в кэше «следов», доступном для компьютера-сервера, для определения того, содержит ли кэш «следов» совпадающий «след», причем каждый «след» в кэше «следов» содержит заранее заданное время существования, и при этом любой «след», время существования которого истекло, удаляется из кэша «следов» вместе с любой связанной с ним идентификационной информацией об объекте аудиовизуальной информации, в случае если кэш «следов» содержит совпадающий «след», определять, содержит ли совпадающий «след» какую-либо связанную с ним идентификационную информацию об объекте аудиовизуальной информации, и если содержит, то передавать эту идентификационную информацию об объекте аудиовизуальной информации с сервера соответствующему клиенту,
в случае если кэш «следов» не содержит совпадающий «след», осуществлять поиск в базе данных «характерных отпечатков» для определения того, имеются ли какие-либо совпадающие «характерные отпечатки», и сохранять переданный «след» в кэше «следов» вместе с результатами поиска в базе данных, и
в случае если база данных «характерных отпечатков» содержит совпадающий «характерный отпечаток», передавать идентификационную информацию об объекте аудиовизуальной информации, связанную с этим «характерным отпечатком», с сервера соответствующему клиенту.

20. Машиночитаемый носитель информации по п.19, в котором заранее заданное время существования для «следа» в кэше «следов» возвращается в исходное состояние, в случае, когда этот «след» в кэше «следов» совпадает со «следом» потока аудиовизуальной информации.

21. Машиночитаемый носитель информации по п.19, в котором «следы» в кэше «следов», которые часто совпадают с переданными «следами», постоянно поддерживаются в кэше «следов» независимо от заранее заданного времени существования.

22. Машиночитаемый носитель информации по п.19, в котором каждый «след» в кэше «следов» удаляется из кэша «следов» вместе с любой связанной с ним идентификационной информацией об объекте аудиовизуальной информации после того, как в течение заранее заданного промежутка времени он не совпал ни с какими переданными «следами».

23. Машиночитаемый носитель информации по п.19, в котором кэш «следов» имеет фиксированный размер и в котором всякий раз, когда в кэше «следов» сохраняется переданный «след», из кэша «следов» удаляется самый старый в кэше «следов» «след» вместе с любой связанной с ним идентификационной информацией об объекте аудиовизуальной информации.

24. Машиночитаемый носитель информации по п.19, в котором идентификационная информация об объекте аудиовизуальной информации, переданная каждому соответствующему клиенту, содержит остающуюся продолжительность передаваемого в текущий момент потоковым способом объекта аудиовизуальной информации, включенного в захваченный поток аудиовизуальной информации, мониторинг которого осуществляется каждым клиентом, и в котором любой клиент, принимающий такую информацию, временно приостанавливает передачу «следов» компьютеру-серверу на время остающейся продолжительности передаваемого в текущий момент потоковым способом объекта аудиовизуальной информации.