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

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

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

E-mail: 

NEAR-DUPLICATE  VIDEO  RETRIEVAL

Nikitin  Ilya

reseacher  at  online  cinema  Tvzavr  (tvzavr.ru),  Moscow;  postgraduate  student  of  the  Moscow  Aviation  Institute  (National  Research  University)  Moscow

АННОТАЦИЯ

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

ABSTRACT

The  paper  focuses  on  an  approach  to  a  near-duplicate  videos  search.  The  search  is  based  on  the  comparison  of  scene  relative  lengths  in  the  space  L2.  The  comparison  is  made  with  Gale-Church  hypothesis.  The  concept  "shot  descriptor"  was  introduced.  To  speed  up  the  performance  of  this  method,  semantic  hashing  was  suggested,  i.e.  a  generalization  of  locally  sensitive  hashing.

Ключевые  слова:  алгоритмы;  видео;  нечеткие  дубликаты;  GIST;  SIFT;  МОВ;  кадры;  съемки;  сцены;  алгоритм  Гейла-черча;  ЛЧХ;  ограниченная  машина  Больцмана,  дескриптор  сцены.

Keywords:  algorithms;  video;  near-duplicates;  GIST;  SIFT;  SVM;  frames;  shots;  scenes,  Gale-Church  algorithm;  LSH;  Restricted  Boltzmann  machine;  shot  descriptor;  scene  descriptor.

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

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

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

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

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

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

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

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

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

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

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

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

Таблица  1.

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

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

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

Таблица  2.

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

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

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

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

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

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

Таким  образом,  получили  дескриптор  сцены.  Он  состоит  из  вектора  отношений  длины  сцены  к  длинам  других  сцен  и  характеристик  начального  и  конечного  кадров.  Его  удобно  его  сразу  хранить,  с  объединениями  соседних  сцен  (трех  предыдущих)  учитывая  гипотезу  Гейла-Черча. 

Сравнивать  дескрипторы  явно  —  не  эффективно.  Предлагается  применить  бинарные  подписи.  Подписи  должны  быть  близки  для  близких  дескрипторах  в  L2.  Такие  подписи  называют  семантическими  хешами.  Самое  простое,  что  можно  предложить:  —  локально  чувствительные  хеши  (ЛЧХ  —  LSH,  locally  sensitive  hashing).  Пространство  дескрипторов,  делим  гиперплоскостью  на  два  подпространства.  Назначаем  дескрипторам  этих  подпространств  подпись  «нуль»  или  «единица».  Получили  бит  подписи.  С  увеличением  числа  бить  ассимптотически  приближаем  метрику  L2.  Для  задач  подобного  рода  лучше  себя  показали  обучаемые  хеши.  К  ним  относится  ограниченная  машина  Больцмана  (Restricted  Boltzmann  machine)  —  вероятностная  рекуррентная  нейронная  сеть.  Вероятностная  версия  сети  Хопфилда  или  нейросетевая  версия  Скрытой  Модели  Маркова  (Hidden  Markov  Model).  Применяется  модификация,  без  связей  внутри  слоев.  Мощность  слоев  понижается  от  размера  входного  вектора  до  размера  требуемого  кода.

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

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

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