ПОИСК  НЕЧЕТКИХ  ДУБЛИКАТОВ  ВИДЕО  НА  ОСНОВЕ  СЦЕН

Никитин  Илья  Константинович

математик  в  Интернет-кинотеатре  Tvzavr  (tvzavr.ru),  г.  Москва;  аспирант  Московского  Авиационного  Института  (НИУ),  г.  Москва

E-mail: 

В  работе  рассмотрен  подход  для  поиска  нечетких  дубликатов  видео.  Поиск  основан  на  сравнении  относительных  длин  сцен  в  пространстве  L2.  Сравнение  проводится  с  учетом  гипотезы  Гейла-Черча.  Вводится  понятие  «дескриптора  сцены».  Для  ускорения  работы  метода  предложено  использовать  семантическое  хеширование,  обобщение  локально  чувствительного  хеширования.

Введение

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

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

Проблема  нечетких  дубликатов  тесно  связана  с  проблемами  классификации  видео  и  поиска  по  видео.  Но  эти  задачи  являются  самостоятельными.

Предшествующие  разработки

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

На  данный  момент  нечеткие  дубликаты  пытаются  искать,  сравнивая  глобальные  особенности  видео  (функция  яркости,  функция  визуального  потока),  глобальные  (гистограммы,  спектры,  GIST)  и  локальные  (PCA-SIFT,  детектор  Харриса)  особенности  кадров  и  множеств  кадров.  Сравнивают  звуковой  ряд  (например,  так  делают  в  youtube.com).  Ищут  и  сравнивают  «визуальные  слова»,  характерные  последовательности  действий  в  кадре  (например,  так  делают  в  licenzero.ru).  Используется  комбинация  методов.

Последние  годы  были  предложены  подходы,  использующие  временную  информацию  в  видео  [1,  2].

Формальная  постановка  задачи

Дан  набор  видео,  для  нового,  добавляемого  в  этот  набор  видео  нужно  определить  есть  ли  дубликат  этого  нового  видео  в  наборе  или  нет. 

Предполагаемое  решение

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

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

Выделение  сцен  происходит  на  основе  трех  базовых  подходов:  сравнение  гистограмм  соседних  кадров;  спектров  кадров  и  векторов  оптического  потока. 

Рисунок  1:  Первые  кадры  сцен  некоторого  видео

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

Таблица  1.

Временные  отметки  перемены  сцен,  в  секундах,  для  видео,  сжатых  разными  кодеками  (проведено  при  низкой  чувствительности  деления  на  сцены)

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

Относительные  длины  сцен  двух  нечетких  дубликатов  редко  будут  совпадать.  Более  того,  многие  сцены  могут  просто  не  распознаваться.  Это  связано,  в  том  числе,  с  ошибками  распознавания  границ  сцен. 

Таблица  2.

Временные  отметки  перемены  сцен,  в  секундах,  для  видео,  сжатых  разными  кодеками  (проведено  при  высокой  чувствительности  деления  на  сцены)

Если  относительная  длина  сцены  одного  видео  отличается  от  длины  сцены  другого  видео  не  более  чем  в  два  раза,  и  все  предыдущие  сцены  выравнены,  то,  текущая  пара  сцен  выражает  одно  и  то  же  явление,  при  условии,  что  оба  видео  являются  нечеткими  дубликатами  друг  друга  (гипотеза  Гейла-Черча  [3]).  Подобный  подход  применяется  в  математической  лингвистике  для  выравнивания  параллельных  корпусов  текстов  на  разных  языках. 

Автор  считает,  что  два  нечетких  дубликата  видео  являются  «переводами»  друг  друга.  Требуется  установить  близость  таких  «переводов».

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

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

GIST  —  простой,  но  не  очень  точный  способ  глобального  описания  изображения.  Изначально  используется  для  поиска  похожих  изображений.  Считаем  отклики  детекторов  краёв  на  5  разных  масштабах  и  6  ориентациях  края.  Получаем  33  «канала»  —  цвет  и  30  откликов  фильтров  края.  Разбиваем  изображение  сеткой  4  ×  4  на  16  ячеек.  В  каждой  ячейке  усредняем  значения  всех  каналов.  Применим  для  широкого  круга  задач. 

«Мешок  слов»,  более  точен,  при  достаточном  размере  словаря.  Необходимо,  чтобы  был  набор  изображений,  на  которых  можно  обучиться.  Обучение:  собираем  множество  фрагментов  (на  основе  SIFT);  кластеризуем  и  строим  словарь;  квантуем  каждый  фрагмент  по  словарю;  считаем  «мешки  слов»  для  каждого  изображения;  обучаем  метод  опорных  векторов  на  мешках  слов.  Сопоставление:  выбираем  фрагменты  из  изображения  (на  основе  SIFT);  квантуем  каждый  фрагмент  по  словарю;  строим  «мешок  слов»  для  изображения;  применяем  классификатор  на  основе  метода  опорных  векторов.  «Мешок  слов»  хорош,  если  работа  ведется  только  в  рамках  конкретной  предметной  области.  Но  работает  медленнее  и  потенциально  бесконечен  по  памяти.  В  случае  БПЛА  разумнее  использовать  «мешок  слов»,  а  для  общего  назначения  —  GIST.

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

Заключение

Был  предложен  подход  поиска  нечетких  дубликатов  видео  на  основе  сцен.  Основные  моменты:  относительные  длины  сцен,  выравнивания  сцен  на  основе  гипотезы  Гейла-Черча,  дескрипторы  сцен.  Проведен  ряд  экспериментов,  которые  показали,  что  при  использовании  предварительной  обработки  метод  справляется  с  поиском  на  относительно  большой  базе  видео  (6000  полнометражных  фильмов)  за  приемлемое  время  (менее  секунды).

Список  литературы:

1.Belkhatir  M.,  Tahayna  B.  Near-duplicate  video  detection  featuring  coupled  temporal  and  perceptual  visual  structures  and  logical  inference  based  matching.  Information  Processing  and  Management  (2011),  —  doi:10.1016/j.ipm.2011.03.003.

2.Глазистов  И.В.,  Паршин  А.Е.,  Алгоритм  поиска  дубликатов  в  базе  видеопо-следовательностей  на  основе  сопоставления  иерархии  смен  сцен,  —  М.:  ВмиК  МГУ,  2010  г.

3.Gale  A.,  Church  W.,  A  program  for  aligning  sentences  in  bilingual  corpora,  Proceedings  of  the  29th  annual  meeting  on  Association  for  Computational  Linguistics,  pp.  177—184  —  Berkeley:  ACL’91.