Практикум на ЭВМ (317)/2013-2014/BackgroundSubtraction

Материал из MachineLearning.

(Различия между версиями)

Версия 15:15, 2 декабря 2013

Статья в настоящий момент дорабатывается.
Это предварительная версия задания. Пока не сто́ит приступать к выполнению.

Содержание

1 Восстановление плотности распределений. Вычитание фона

Восстановление плотности распределений. Вычитание фона

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

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

Данные

Вам предлагается использовать стандартные тестовые последовательности с веб-сайта ChangeDetection.net. Два набора данных являются обязательными:

Baseline/pedestrians (train — 1:299; test — 300:1099),
Camera jitter/traffic (train — [581:723, 752:951]; test — 1000:1570).

Вы можете использовать и другие последовательности для лучшего изучения свойств методов.

Оценка алгоритмов

Для каждого кадра тестовой части последовательности можно оценить качество алгоритма, зная его верную разметку (директория groundtruth). Обратите внимание, что только часть каждого из кадров является областью интереса. Например, на последовательности traffic область интереса ограничивается дорогой. Зная, какие части изображения на самом деле относятся к фону (класс static) и к переднему плану (класс motion), можно оценить количество верных положительных (TP) и отрицательных (TN) обнаружений пикселей, а также ложноположительных (FP) и ложноотрицательных (FN).

Здесь можно скачать функции для подсвечивания маски переднего плана (highlightMask.m) и «проигрывания видео» (showvid.m), которые могут быть полезны для визуальной оценки качества. Пример работы функции highlightMask:

Реализация

Одномерная гауссиана

В самом простом варианте можно моделировать распределение цвета в каждом пикселе одномерным нормальным распределением. Для этого нужно перевести видеопоследовательность в полутоновую. Это можно сделать, например, с помощью формулы из стандарта NTSC: $\mathit{bw} = 0.2126r + 0.7152g + 0.0722b$ . Для каждого пикселя обучающей части последовательности оцените параметры нормального распределения, используя яркости в каждой позиции пикселя (например, для pedestrians будет 299 точек для оценки плотности в каждом пикселе). Обратите внимание, что некоторые гауссианы получаются вырожденными. Для регуляризации разумно ограничивать возможное значение среднеквадратичного отклонения снизу. Можно использовать $\sigma_{\min} = 5$ . Далее, при классификации пикселя тестовой выборки, его нужно относить к фону тогда и только тогда, когда его яркость отклоняется от μ меньше, чем на kσ. Если установить k = 3, ожидается, что к переднему плану будут отнесены только 0.27% пикселей фона («правило 3σ»). Изменяя этот порог, можно регулировать соотношение между количеством ложноположительных и ложноортицательных обнаружений.

Реализуйте такую оценку фона и запустите на последовательности pedestrians. Проанализируйте качество вычитания фона с помощью трёх инструментов:

Для каждого тестового кадра посчитайте количество ошибок 1 рода (FP) и 2 рода (FN). Постройте график зависимости ошибок от номера кадра. Какой эффект наблюдается?
Проведите визуальную оценку. Для этого на каждом из кадров выделите области, отнесённые к переднему плану. Сделайте вывод о характере ошибок.
Проведите оценку величин TPR и FPR (доли верноположительных и ложноположительных обнаружений, соответственно) по всей тестовой последовательности (не усредняя по кадрам) и постройте графики ROC характеристики. Это будет необходимо для сравнения различных моделей.

Оценка гауссианы на лету

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

Реализуйте следующий итеративный алгоритм оценки параметров гауссовской модели фона на лету (оценка также производится по полутоновым изображениям независимо для разных пикселей):

Инициализировать $\mu_0, \sigma^2_0, t = 0$ .
Принять решение о метке пикселя на кадре t: передний план тогда и только тогда, когда $\frac{|(I_t-\mu_t)|}{\sigma_t} > k$ , где $I_t$ — яркоcть пикселя на кадре t.
Если пиксель отнесён к фону, обновить $\mu_{t+1} = \rho I_{t+1} + (1 - \rho) \mu_ {t}$ , иначе $\mu_{t+1} = \mu_t$ .
Если пиксель отнесён к фону, обновить $\sigma^2_{t+1} = (I_{t+1}-\mu_{t+1})^ 2 \rho + (1 - \rho) \sigma ^ 2_ {t}$ , иначе $\sigma ^ 2_{t+1} = \sigma ^ 2_t$ .
Если не последний кадр, t += 1, перейти на шаг 2.

Новый параметр ρ отвечает за величину памяти метода (размер окна): чем меньше ρ, тем большее влияние имеют старые кадры. Рекомендуемые значения: ρ = 0.01, $\mu_0$ равен яркости на первом кадре, $\sigma^2_0 = 100$ . Не забывайте про регуляризацию: устанавливайте минимальное значение дисперсии.

Протестируйте метод на последовательности pedestrians и повторите анализ из предыдущего пункта. Сделайте вывод о сравнении методов.

Теперь в 3D!

Предлагается изменить модель фона на более гибкую: нормальное распределение в цветовом пространстве RGB с полной матрицей ковариаций. Оцените параметры на обучающей части (в оффлайн-режиме), не забывая о регуляризации матрицы ковариаций (можно добавлять положительное число к диагонали, например, 5). Решение о метке пикселя тестового кадра принимается сравнением плотности нормального распределения в данной точке с порогом.

Постройте ROC кривую для последовательности pedestrians, выберите значение порога и проанализируйте ошибки метода. Сделайте вывод о сравнении метода с остальными.

Запустите метод на последовательности traffic, которая примечательна сильной тряской камеры. Проанализируйте ошибки метода.

Смесь гауссиан

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

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

Замечание. Разделение смеси гауссиан может занять много времени. Уделите внимание оптимизации кода. Отлаживайте код на части изображения.

Дополнительная часть

Приветствуется реализация и оценка модификаций приведённых моделей и алгоритмов. За интересные модификации начисляется до 1 бонусного балла (субъективно и безапелляционно). При этом учитываются критерии:

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

Материалы

Источник — «http://poligon.machinelearning.ru/wiki/index.php?title=%D0%9F%D1%80%D0%B0%D0%BA%D1%82%D0%B8%D0%BA%D1%83%D0%BC_%D0%BD%D0%B0_%D0%AD%D0%92%D0%9C_%28317%29/2013-2014/BackgroundSubtraction»

Категория: Учебные задачи

@@ Строка 53: / Строка 53: @@
 === Теперь в 3D! ===
-Предлагается изменить модель фона на более гибкую: нормальное распределение в цветовом пространстве RGB с полной матрицей ковариаций. Оцените параметры на обучающей части (в оффлайн-режиме). Решение о метке пикселя тестового кадра принимается сравнением плотности нормального распределения в данной точке с порогом.
+Предлагается изменить модель фона на более гибкую: нормальное распределение в цветовом пространстве RGB с полной матрицей ковариаций. Оцените параметры на обучающей части (в оффлайн-режиме), не забывая о регуляризации матрицы ковариаций (можно добавлять положительное число к диагонали, например, 5). Решение о метке пикселя тестового кадра принимается сравнением плотности нормального распределения в данной точке с порогом.
 Постройте ROC кривую для последовательности pedestrians, выберите значение порога и проанализируйте ошибки метода. Сделайте вывод о сравнении метода с остальными.