An adaptive video-stream's scene boundaries detector and method of its learning based on the video stream's co.pdf Достижения в области сжатия потокового видео и рост пропускной способности каналов сети Интернет привели к широкому распространению интернет-сервисов, связанных с той или иной формой обработки видеоданных. Рост объёмов накапливаемых массивов видеоданных требует эффективных инструментов их индексации для последующей разработки различных систем контекстного поиска и других сервисов. Разбиение видеопотока на сцены (shorts, scenes) - неразрывные последовательности кадров, снятые одной камерой и поддающиеся интерпретации, - является одной из первых процедур его обработки. В дальнейшем извлечённые сцены могут использоваться для индексации, кластеризации, распознавания объектов и людей и т. д. Существует несколько типов процесса смены сцены: резкая, или мгновенная, смена сцены (abrupt, или cut) является результатом последовательного соединения двух различных сцен; плавная смена сцены (gradual transition) продолжается несколько кадров и является результатом применения специальных видеоэффектов, таких как затемнение (fade-in), просветление (fade-out), растворение (dissolve) и т.д. В данной работе рассматривается задача обнаружения моментов мгновенной смены сцен, которая формулируется следующим образом: требуется построить детектор (классификатор), который каждый кадр видео-потока относит либо к классу 1 (первый кадр сцены), либо к классу 0 (внутренний кадр сцены). В работе [1] сделан большой обзор подходов к решению этой задачи. В основе большинства подходов [2-7] лежит применение специальных функций, которые принято называть метриками и которые количественно оценивают схожесть кадров. Если у близлежащих кадров значение метрики мало, т.е. кадры похожи, то, скорее всего, они относятся к одной сцене; если же значение метрики велико, то кадры существенно отличаются друг от друга и, возможно, принадлежат разным сценам. Превышение значения метрики заданного порогового значения Tm интерпретируется как сигнал о начале новой сцены. Таким образом, задача построения детектора сводится к выбору метрики и порогового значения. Естественно, в работе детектора возможны ошибки: момент смены сцены может детектироваться тогда, когда его нет (ложное срабатывание, false positive); момент смены сцены не детектируется (пропуск, false negative). Пусть по результатам обработки видеопотока детектором стали известны следующие величины: TN - количество верно классифицированных кадров класса 0, FP - количество ложных срабатываний, FN - количество пропусков и TP - количество верно классифицированных кадров класса 1 и пусть P и N - количество кадров видеопотока, принадлежащих классу 1 и классу 0 соответственно, тогда для оценки качества работы детектора можно использовать следующие показатели: „ TP TN . TP TP „ Precision • Recall Se =-, Sp =-, Precision =-, Recall =-, F1 = 2-, (!) P N TP + FP TP + FN Precision + Recall которые называются соответственно чувствительность, специфичность, точность, полнота и F-мера. Значения всех показателей лежат в интервале [0; 1]. Чем точнее работает детектор, тем ближе к единице значения этих показателей. В работе [8] предложен подход, позволяющий повысить качество работы детектора путём разбиения кадров видеопотока на непересекающиеся прямоугольные блоки. Суть подхода состоит в следующем. Для каждой пары одинаково расположенных блоков близлежащих кадров вычисляется значение метрики. Если её значение превышает пороговое значение Tm, то считается, что блок сигнализирует о наличии смены сцены; если доля таких блоков превышает заданное пороговое значение Tb, то детектор принимает решение об обнаружении момента смены сцены. На качество работы детектора влияют выбор метрики и количество блоков, на которые разбивается кадр, выбор пороговых значений Tb и Tm и характер содержимого видео-потока. Причём последнее обстоятельство существенно ограничивает возможности построения полностью автоматизированных систем разбиения видеопотоков на сцены. Устранению этого ограничения посвящена данная работа. 1. Метрики и эвристики, используемые при построении детектора Прежде чем описывать методологию построения детектора, необходимо отметить, что её разработка велась в компании TomskLabs (http://www.tomsklabs.com) в рамках работ по созданию системы видеоклассификации. На начальном этапе были изучены и опробованы некоторые известные методы решения данной задачи; подход, предложенный в работе [8], был признан удачным и лёг в основу разрабатываемого детектора; также были сделаны следующие выводы: 1. Увеличение количества блоков, на которые следует разбивать кадры, с 4 (2x2) до 100 (10x10) приводит к заметному повышению качества работы детектора, дальнейшее же увеличение количества блоков неэффективно. В данной работе используется разбиение на 100 (10x10) блоков. 2. Хорошие результаты показали следующие метрики: ^ (n) = E (n)" E (n -1)|, (2) S 1 (n)=(n) - Sj (n -1)|, (3) где E(n) и Sij(n) - соответственно среднее значение и среднеквадратичное отклонение яркостей пикселей (i, /)-го блока кадра с номером n (предполагается, что кадры видеопотока представлены в градациях серого цвета, преобразование выполняется простым усреднением RGB-компонент, максимально возможное значение яркости одного пикселя равно 255). Решающее правило детектора при использовании этих метрик имеет вид: если значение одной из метрик (1) или (2) превысит заданное пороговое значение Tm, то принимается решение, что (i,/)-й блок кадра с номером n сигнализирует о смене сцены. 3. Пороговые значения Tb и Tm следует выбирать из интервалов [0,2; 0,8] и [0,03; 0,07] соответственно. 4. При выборе пороговых значений Tb и Tm следует обращать внимание на такие признаки видеопотока, как тёмный / светлый и спокойный / динамичный. Если фрагмент видеопотока состоит из тёмных кадров и события в нём разворачиваются медленно, то пороговые значения Tb и Tm следует выбирать ближе к левому краю указанных интервалов, а если кадры светлые и события происходят быстро, то, наоборот, - ближе к правому краю. Во всех остальных случаях значения порогов следует выбирать из середины интервалов. Из последнего вывода следует, что должны иметь место зависимости Tm = f(Tb) и Tb = g(L, D), где L и D - некоторые величины, количественно описывающие такие характеристики фрагмента видеопотока, как тёмный / светлый и спокойный / динамичный соответственно. Для оценки величины L необходимо уметь оценивать яркость одного кадра. Для этой цели естественно использовать нормированное среднее значение яркостей пикселей кадра 1 1 w h E (n) =--УУ p„ (n), 255 whj~\ j-( ] где pij(n) - значение яркости (i, j)-ro пикселя кадра с номером n; w и h - соответственно ширина и высота кадра в пикселях. Для оценки величины D необходимо уметь оценивать степень произошедших изменений в двух последовательных кадрах, для этого была разработана метрика 0, n < 0, Д( n) = < 1, n = 1, -2 (Ah (n) + AV (n)), n >1, где 1 1 nh nv -1 Ah (n) = -(Z-ITS S I (Eij (n) - Ei, j+1 (n)) - Ej (n - 1) - Ej +1 (n - 1)) | , 510 Пh (nv 1) i=1 j=1 л л nh-1 nv A (n) = J^nPn, S S'( E'j (n) - Emj (n)) - (Eu (n -1) - E'+h} (n - ^ Ej(n) - среднее значение яркости пикселей его (i, j)-го блока кадра с номером n; nh и nv - количество блоков по горизонтали и по вертикали, на которые разбивается кадр. Так как видеопоток, как правило, не является однородным (некоторые его фрагменты могут быть, например, светлыми и динамичными, другие - тёмными и спокойными), то оценку величин L и D следует производить отдельно для каждого кадра, опираясь на данные близлежащих кадров. В работе для этой цели использовалось простое усреднение метрик E(n) и A(n) по k предыдущим и k последующим кадрам: 1 k L(n, k) = -- S E(n + i), (4) 2k +1 • » -k k 1 D(n, k) = -S A(n + i). (5) 2k +1 i=-k Экспериментально установлено, что при использовании метрик (2), (3) и указанном методе оценивания величин L и D упомянутые выше зависимости f и g хорошо описываются линейной и правой полулогарифмической моделями соответственно, т.е. f(Tb) = ao +alTb, (6) g (L, D) = bo + b ln(L) + b2ln(D), (7) где a0, a1, b0, b1, b2 - параметры, значения которых необходимо найти. При использовании формул (6)-(9) необходимо учитывать следующее: 1. При вычислении величин L(n, k) и D(n, k) для первых и последних кадров потока в формулах (4) и (5) необходимо изменить пределы суммирования и соответствующим образом нормирующий множитель, чтобы избежать выхода за границы видеопотока. 2. Так как экспериментально установлено, что пороговые значения Tb и Tm должны находиться внутри интервалов [0,2; 0,8] и [0,03; 0,07] соответственно, то вычисляемые по формулам (6) и (7) значения необходимо скорректировать следующим образом: Tb = max(0,2; min(0,8; g(L, D)), (8) Tm = max(0,03; min(0,07; f (Tb)). (9) 3. Величины L(n) и D(n) могут принимать нулевые значения, если, например, в видеопотоке имеются полностью чёрные кадры или последовательность полностью идентичных кадров, тогда воспользоваться формулой (7) для расчёта порогового значения Tb нельзя. В этом случае пороговое значение Tb следует установить равным 1. 2. Алгоритм работы адаптивного детектора моментов мгновенной смены сцены Алгоритм работы предлагаемого детектора для каждого обрабатываемого кадра видеопотока производит подбор оптимальных пороговых значений Tb и Tm, опираясь на признаки тёмный / светлый и спокойный / динамичный близлежащих кадров. Псевдокод алгоритма имеет следующий вид: Вход: последовательность кадров видеопотока, параметр к. Выход: размеченная последовательность кадров. 1. Объявить первый кадр видеопотока начальным кадром новой сцены. 2. Для каждого кадра с номером n > 1 делать: 2.1. Вычислить значения величин L(n, к) и D(n, к) по формулам (4), (5). 2.2. Вычислить пороговые значения Tb и Tm по формулам (6), (7). 2.3. Скорректировать пороговые значения Tb и Tm по формулам (8), (9). 2.4. Для каждого блока кадра делать: 2.4.1. Вычислить значения метрик це(п) и ц5(п) по формулам (2) и (3). 2.4.2. Если це(п) > Tm или ц5(п) > Tm, то объявить блок сигнализирующим о смене сцены. 3. Если доля блоков кадра, сигнализирующих о смене сцены, превышает пороговое значение Tb, то объявить текущий кадр начальным кадром новой сцены, иначе объявить текущий кадр внутренним кадром сцены. 3. Обучение детектора Для работы адаптивного детектора требуются значения параметров a0, ab b0, bb b2, входящих в формулы (6), (7). Для их нахождения предлагается процедура обучения детектора, в основе которой лежат три ключевых момента: 1. Для решения задачи требуется обучающая выборка однородных видеопотоков. 2. Для каждого видеопотока обучающей выборки необходимо определить степень выраженности признаков тёмный / светлый и спокойный / динамичный. 3. Для каждого видеопотока обучающей выборки необходимо определить оптимальные пороговые значения Tb и Tm. Однородность видеопотоков выборки будем понимать в том смысле, что каждый видеопоток может быть отнесён лицом, осуществляющим обучение детектора, к одному из четырёх классов тёмный-спокойный, тёмный-динамичный, светлый-спокойный, светлый-динамичный. Добиться такого свойства от выборки можно путём «нарезки» предназначенных для включения в выборку изначально неоднородных видеопотоков на короткие однородные фрагменты. Пусть XL = [xi | i = 1,...,Nl} - репрезентативная выборка однородных видеопотоков. Степень выраженности признаков тёмный / светлый и спокойный / динамичный видеопотока xi определим путём усреднения по всем кадрам видеопотока значения метрик E(n) и A(n) соответственно, т.е. 1 ni 1 ni L = - £ E(n) и Dx = - ^A(n), (12) ni t! ni tf где n - количество кадров в видеопотоке хг-. Оптимальность пороговых значений Tbi и Tmi видеопотока xt будем понимать в смысле минимума суммарной ошибки (FN + FP) детектора с фиксированными порогами, псевдокод алгоритма работы которого имеет следующий вид: Вход: последовательность кадров видеопотока, параметры Tb и Tm. Выход: размеченная последовательность кадров. 1. Объявить первый кадр видеопотока начальным кадром новой сцены. 2. Для каждого кадра с номером n > 1 делать: 2.1. Для каждого блока кадра делать: 2.1.1. Вычислить значения метрик цЕ и ц5 по формулам (2) и (3). 2.1.2. Если цЕ > Tm или ц5 > Tm, то объявить блок сигнализирующим о смене сцены. 3. Если доля блоков кадра, сигнализирующих о смене сцены, превышает пороговое значение Tb, то объявить текущий кадр начальным кадром новой сцены, иначе объявить текущий кадр внутренним кадром сцены. Алгоритм работы детектора с фиксированными порогами отличается от алгоритма адаптивного детектора отсутствием шагов 2.1-2.3, отвечающих за динамическое обновление пороговых значений Tb и Tm, которые в данном случае являются задаваемыми извне параметрами. Поиск оптимальных пороговых значений Tbi и Tmi для видеопотока xi будем производить путём перебора значений в диапазонах [0,2; 0,8] и [0,03; 0,07] с шагами 0,1 и 0,01 соответственно и вычисления для каждой пары пороговых значений суммарной ошибки (FN + FP) детектора с фиксированными порогами. Выполнив перебор, получим множество, в котором каждый элемент состоит из пары (Tbi, Tmi) и соответствующего значения суммарной ошибки. Извлечём из этого множества подмножество «топ-5», состоящее из пар (Tbi, Tmi), соответствующих пяти наименьшим значениям суммарной ошибки (таких пар может быть несколько), и выберем в качестве оптимальных пороговых значений Tb и Tm центральную точку этого подмножества (рис. 1). 0,1 0,08 0,06 Tm 0,04 0,02 0 Рис. 1. Множество «топ-5» (белые точки) и его центральная точка (чёрная точка) для одного из видеопотоков обучающей выборки В результате выполнения описанной процедуры получим набор {Li, Di, Tbi, Tmi, | i = 1,..., NL}, используя который найдём методом наименьших квадратов оценки параметров a0, ab b0, bb b2. 4. Эксперимент на реальных данных Для проверки работоспособности предложенного метода построения адаптивного детектора мгновенной смены сцен была подготовлена выборка, состоящая из фрагментов популярных художественных фильмов. Источником первичных данных являлся сайт youtube.com. С него было загружено 20 фрагментов, из которых было «нарезано» 27 видеопотоков, содержащих только мгновенные смены сцен. Длина каждого видеопотока составляла 1 499 кадров, что соответствует примерно одной минуте видео (скорость воспроизведения в разных видеопотоках варьировалась от 24 до 30 кадров в секунду), общее количество сцен 1 098. Для обучения и оценки качества работы адаптивного детектора исходная выборка «нарезаных» видеопотоков разделялась случайным образом на три равных части: обучающую, валидационную и тестовую. Обучающая выборка использовалась для оценки значений параметров a0, ab b0, bb b2. Валида-ционная выборка использовалась для определения оптимального в смысле минимума суммарной ошибки адаптивного детектора на валидационной выборке значения параметра к (поиск проводился в интервале [1; 30] с шагом 1). Тестовая выборка, хотя и состоящая из однородных видеопотоков, но по сути представляющая собой один большой неоднородный видеопоток, использовалась для объективной оценки качества работы детектора. На данных тестовой выборки рассчитывались показатели качества Se, Sp, Precision и F1 (1). Для полноты картины на тех же тестовых данных производилась оценка качества работы детектора с фиксированными порогами при Tb = 0,6 и Tm = 0,06 и гипотетического (наилучшего) детектора, алгоритм работы которого отличался от алгоритма детектора с фиксированными порогами тем, что для каждого видеопотока, входящего в тестовую выборку, использовались соответствующие оптимальные пороговые значения Tb и Tm. Было проведено 1 000 экспериментов. Их результаты представлены на рис. 2, 3 и в табл. 1, 2. ; ; _ 000 1 о!> о ---|---о о: Фо _ 0 0,2 0,4 0,6 0,8 1 Tb Адаптивный детектор Se Ч I I----H Детектор с фиксированными порогами Sp Precision *------СШ1-:н ^-------- I l-i-- F1 -со--? 0.6 0.8 1 0.96 0.98 1 0.4 0.7 1 0.5 0.75 Гипотетический детектор Рис. 2. Гистограммы распределения показателей качества работы различных детекторов На рис. 2 приведены гистограммы распределения значений показателей качества работы трёх детекторов. К каждой гистограмме добавлены стандартная диаграмма размаха соответствующего показателя и вертикальная пунктирная линия, соответствующая среднему значению показателя гипотетического (наилучшего) детектора. В табл. 1 представлены основные статистические характеристики показателей качества работы детекторов: средние значения и среднеквадратичные отклонения. Т а б л и ц а 1 Основные статистические характеристики показателей качества работы детекторов Тип детектора Характеристика Se Sp Pr F1 Адаптивный Среднее 0,9213 0,9983 0,9428 0,9295 с.к.о. 0,0595 0,0019 0,055 0,0374 С фиксированными порогами Среднее 0,8452 0,9918 0,7563 0,7918 с.к.о. 0,079 0,0046 0,1096 0,0693 Гипотетический (наилучший) Среднее 0,9512 0,9978 0,9234 0,9369 с.к.о. 0,0166 0,0007 0,0239 0,0165 Интерес также представляет то, как соотносятся между собой показатели качества работы детекторов в каждом отдельно взятом эксперименте. На рис. 3 приведены гистограммы разностей значений соответствующих показателей качества адаптивного детектора и детектора с фиксированными порогами (вверху) и адаптивного детектора и гипотетического детектора (внизу), вычисленные по результатам каждого эксперимента. К каждой гистограмме добавлены стандартная диаграмма размаха разности показателей и вертикальная пунктирная линия, соответствующая нулевому значению; столбцы гистограмм, расположенные правее этой линии, свидетельствуют в пользу адаптивного детектора. В табл. 2 представлены основные статистические характеристики разностей значений показателей качества - их средние значения и среднеквадратичные отклонения, а также указаны доли от общего количества экспериментов, в которых эти разности положительны и превышают значение -0,05. Сравнение адаптивного детектора с детектором с фиксированными порогами Se Sp Precision F1 Ч----j-Ш--н I-t-Ш-------1 I--j-СПИ--н ч-i-ш- 0.4 -0.02 0.02 -0.5 0.5 -0.4 Сравнение адаптивного детектора с гипотетическим детектором 0.4 Рис. 3. Гистограммы распределения разности значений показателей качества работы различных детекторов 0 0 0 Т а б л и ц а 2 Сравнение качества (случай адаптивного детектора с оптимальным значением параметра к) Вариант сравнения Характеристика ASe ASp APr AF1 Адаптивный детектор против детектора с фиксированными порогами Среднее 0,0762 0,0065 0,1865 0,1376 с.к.о. 0,0752 0,0044 0,1012 0,0654 Доля > 0 83,5% 98,1% 98,5% 98,4% Доля > -0,05 95% 100% 99,6% 99,9% Адаптивный детектор против гипотетического детектора Среднее -0,0299 0,0005 0,0194 -0,0075 с.к.о. 0,0599 0,0018 0,0485 0,036 Доля > 0 35,5% 80,4% 81,3% 50,9% Доля > -0,05 70,7% 100% 91,7% 88,9% Проанализировав графики на рис. 2, 3 и данные табл. 1, 2, можно сделать вывод, что адаптивный детектор демонстрирует качество работы, близкое к качеству работы гипотетического (наилучшего) детектора - среднее значение его чувствительности на 3% меньше среднего значения чувствительности гипотетического детектора при сравнимой точности классификации, в то время как у детектора с фиксированными порогами при сопоставимой чувствительности точность составляет около 50%; в 35,5% от общего числа экспериментов адаптивный детектор продемонстрировал лучшую чувствительность, чем у гипотетического (наилучшего) детектора и в 70,7% уступил ему не более чем на 5% при сопоставимых значениях других показателей качества. В описанных выше экспериментах оптимальное значение параметра k определялось на основе данных валидационной выборки. На рис. 4 представлены гистограмма распределения и диаграмма размаха оптимальных значений параметра, вертикальные пунктирные линии соответствуют среднему значению 11,85. Представляет интерес, как изменились бы показатели качества работы адаптивного детектора при фиксированном значении параметра k. Для ответа на данный вопрос были проведены две дополнительные серии экспериментов с тем же самым разбиением на обучающую, валидационную (не использовалась) и тестовую выборки при фиксированных значениях k = 6 и k = 12. В табл. 3 представлены основные статистические характеристики разностей значений показателей качества адаптивного детектора и гипотетического (наилучшего) детектора - их средние значения, среднеквадратичные отклонения и доли от общего количества экспериментов, в которых указанные разности положительны и К I----гтг~ь-----------Н - 0 15 30 Рис. 4. Гистограмма распределения оптимального значения параметра к Т а б л и ц а 3 Сравнение качества (случай адаптивного детектора при фиксированном значении параметра к) Вариант сравнения Характеристика ASe ASp APr AF1 Адаптивный детектор с фиксированным значением к = 6 против гипотетического детектора Среднее -0,0364 0,0006 0,0232 -0,0095 ^к.о. 0,0691 0,0018 0,0496 0,0411 Доля > 0 34,5% 82,4% 83,1% 51,7% Доля > -0,05 68,4% 100% 92,6% 86,9% Адаптивный детектор с фиксированным значением к = 12 против гипотетического детектора Среднее -0,0262 0,0005 0,0195 -0,0055 ^к.о. 0,0599 0,0018 0,0485 0,0361 Доля > 0 38,1% 79,3% 79,7% 54,2% Доля > -0,05 73,7% 100% 91,6% 90,1% Заключение В данной работе предложен алгоритм работы адаптивного детектора моментов мгновенной смены сцены в видеопотоке, использующий признаки тёмный / светлый, спокойный / динамичный, и предложен метод его обучения. Эксперимент на выборке из фрагментов художественных фильмов подтвердил работоспособность предложенного подхода. Направлениями дальнейших исследований можно назвать повышение чувствительности адаптивного детектора и изучение его свойств на выборках с более широким спектром содержимого (спортивные передачи, новости...). превышают значение (-0,05). Сравнив данные табл. 2 и 3, можно сделать вывод, что и при фиксированном правильно выбранном значении параметра к качество работы адаптивного детектора близко к качеству гипотетического (наилучшего) детектора.

Скачать электронную версию публикации