Практикум на ЭВМ (317)/2013-2014/BackgroundSubtraction
Материал из MachineLearning.
(→Оценка гауссианы на лету) |
|||
| (17 промежуточных версий не показаны.) | |||
| Строка 1: | Строка 1: | ||
| - | + | < [[Практикум на ЭВМ (317)/2013-2014]] | |
| + | |||
| + | ''Срок сдачи задания — до 22 декабря 2013 г., 23:59. За день просрочки начисляется 0.1 штрафного балла. Задание должно выполняться самостоятельно.'' | ||
| + | |||
= Восстановление плотности распределений. Вычитание фона = | = Восстановление плотности распределений. Вычитание фона = | ||
| - | Вычитания фона — важная прикладная задача. Часто оно является первой стадией в системах анализа видео с камер наблюдения. Необходимо классифицировать пиксели видеопоследовательности на принадлежащие фону и принадлежащие объектам переднего плана. Обычно предполагается, что камера статична. По обучающей выборке необходимо оценить модель фона, чтобы затем для каждого пикселя каждого кадра тестовой видеопоследовательности уметь предсказать вероятность того, что он является фоном. | + | Вычитания фона — важная прикладная задача. Часто оно является первой стадией в системах анализа видео с камер наблюдения. Необходимо классифицировать пиксели видеопоследовательности на принадлежащие фону и принадлежащие объектам переднего плана. Обычно предполагается, что камера статична. По обучающей выборке необходимо оценить модель фона, чтобы затем для каждого пикселя каждого кадра тестовой видеопоследовательности уметь предсказать вероятность того, что он является фоном. Предполагая равномерное распределение на принадлежность пикселей объектам переднего плана (обычно нет априорных сведений, чтобы использовать другое распределение), принятие решения для данного пикселя эквивалентно сравнению предсказанной вероятности фона с некоторым порогом. |
| - | Часто (хотя и не всегда) в качестве обучающей выборки удаётся взять один или несколько кадров, на которых отсутствуют объекты переднего плана. Но даже в этом случае задача оценки модели фона не является тривиальной из-за того, что фон никогда не бывает полностью статичен: всегда есть шум камеры, также может меняться освещение, тени, камера может дрожать, фон может быть динамическим (листва или вода в присутствии ветра), к фону могут добавляться дополнительные объекты. Вам предлагается протестировать несколько моделей разной сложности и | + | Часто (хотя и не всегда) в качестве обучающей выборки удаётся взять один или несколько кадров, на которых отсутствуют объекты переднего плана. Но даже в этом случае задача оценки модели фона не является тривиальной из-за того, что фон никогда не бывает полностью статичен: всегда есть шум камеры, также может меняться освещение, тени, камера может дрожать, фон может быть динамическим (листва или вода в присутствии ветра), к фону могут добавляться дополнительные объекты. Вам предлагается протестировать несколько моделей разной сложности и сделать выводы о применимости моделей в разных ситуациях. |
== Данные == | == Данные == | ||
| - | Вам предлагается использовать стандартные тестовые последовательности с веб-сайта [http://wordpress-jodoin.dmi.usherb.ca/ | + | Вам предлагается использовать стандартные тестовые последовательности с веб-сайта [http://wordpress-jodoin.dmi.usherb.ca/dataset2012 ChangeDetection.net]. Два набора данных являются обязательными: |
* Baseline/pedestrians (train — 1:299; test — 300:1099), | * Baseline/pedestrians (train — 1:299; test — 300:1099), | ||
* Camera jitter/traffic (train — [581:723, 752:951]; test — 1000:1570). | * Camera jitter/traffic (train — [581:723, 752:951]; test — 1000:1570). | ||
| Строка 17: | Строка 20: | ||
== Оценка алгоритмов == | == Оценка алгоритмов == | ||
| - | Для каждого кадра тестовой части последовательности можно оценить качество алгоритма, зная его верную разметку (директория groundtruth). Обратите внимание, что только часть каждого из кадров является областью интереса. Например, на последовательности traffic область интереса ограничивается дорогой. Зная, какие части изображения на самом деле относятся к фону (класс static) и к переднему плану (класс motion), можно оценить количество верных положительных (TP) и отрицательных (TN) обнаружений пикселей, а также ложноположительных (FP) и ложноотрицательных (FN). | + | Для каждого кадра тестовой части последовательности можно оценить качество алгоритма, зная его верную разметку (директория groundtruth). Обратите внимание, что только часть каждого из кадров является областью интереса. Например, на последовательности traffic область интереса ограничивается дорогой. Зная, какие части изображения на самом деле относятся к фону (класс static) и к переднему плану (класс motion), можно оценить количество верных положительных (TP) и отрицательных (TN) обнаружений пикселей, а также ложноположительных (FP) и ложноотрицательных (FN). '''Внимание!''' Пиксели с промежуточными метками (50, 85, 170) не входят в регион интереса и не участвуют в подсчёте точности. Другими словами, значения TP, FP, TN, FN не зависят от того, что вернул алгоритм на этих пикселях. |
| - | + | Можете воспользоваться готовыми функциями для подсвечивания маски переднего плана (<code>highlightMask.m</code>) и «проигрывания видео» (<code>showvid.m</code>), которые могут быть полезны для визуальной оценки качества: [http://www.machinelearning.ru/wiki/images/2/2d/BkgEstimCode.zip zip архив]. Пример работы функции <code>highlightMask</code>: | |
[[Изображение:BkgEstim.jpg]] [[Изображение:BkgEstimG.png]] | [[Изображение:BkgEstim.jpg]] [[Изображение:BkgEstimG.png]] | ||
| Строка 27: | Строка 30: | ||
=== Одномерная гауссиана === | === Одномерная гауссиана === | ||
| - | В самом простом варианте можно моделировать распределение цвета в каждом пикселе одномерным нормальным распределением. Для этого нужно перевести видеопоследовательность в полутоновую. Это можно сделать, например, с помощью формулы из стандарта NTSC: <tex>\mathit{ | + | В самом простом варианте можно моделировать распределение цвета в каждом пикселе одномерным нормальным распределением. Для этого нужно перевести видеопоследовательность в полутоновую. Это можно сделать, например, с помощью формулы из стандарта NTSC: <tex>\mathit{gs} = 0.2126r + 0.7152g + 0.0722b</tex>. Для каждого пикселя обучающей части последовательности оцените параметры нормального распределения, используя яркости в каждой позиции пикселя (например, для pedestrians будет 299 точек для оценки плотности в каждом пикселе). Обратите внимание, что некоторые гауссианы получаются вырожденными. Для регуляризации разумно ограничивать возможное значение среднеквадратичного отклонения снизу. Можно использовать <tex>\sigma_{\min} = 5</tex>. Далее, при классификации пикселя тестовой выборки, его нужно относить к фону тогда и только тогда, когда его яркость отклоняется от μ меньше, чем на ''k''σ. Если установить ''k'' = 3, ожидается, что к переднему плану будут отнесены только 0.27% пикселей фона («правило 3σ»). Изменяя этот порог, можно регулировать соотношение между количеством ложноположительных и ложноортицательных обнаружений. |
Реализуйте такую оценку фона и запустите на последовательности pedestrians. Проанализируйте качество вычитания фона с помощью трёх инструментов: | Реализуйте такую оценку фона и запустите на последовательности pedestrians. Проанализируйте качество вычитания фона с помощью трёх инструментов: | ||
| Строка 33: | Строка 36: | ||
# Для каждого тестового кадра посчитайте количество ошибок 1 рода (FP) и 2 рода (FN). Постройте график зависимости ошибок от номера кадра. Какой эффект наблюдается? | # Для каждого тестового кадра посчитайте количество ошибок 1 рода (FP) и 2 рода (FN). Постройте график зависимости ошибок от номера кадра. Какой эффект наблюдается? | ||
# Проведите визуальную оценку. Для этого на каждом из кадров выделите области, отнесённые к переднему плану. Сделайте вывод о характере ошибок. | # Проведите визуальную оценку. Для этого на каждом из кадров выделите области, отнесённые к переднему плану. Сделайте вывод о характере ошибок. | ||
| - | # Проведите оценку величин TPR и FPR (доли верноположительных и ложноположительных обнаружений, соответственно) по всей тестовой последовательности (не усредняя по кадрам) и постройте графики ROC характеристики. Это будет необходимо для сравнения различных моделей. | + | # Проведите оценку величин TPR и FPR (доли верноположительных и ложноположительных обнаружений, соответственно) для разных значений порога по всей тестовой последовательности (не усредняя по кадрам) и постройте графики ROC характеристики. Это будет необходимо для сравнения различных моделей. |
=== Оценка гауссианы на лету === | === Оценка гауссианы на лету === | ||
| Строка 42: | Строка 45: | ||
# Инициализировать <tex>\mu_0, \sigma^2_0, t = 0</tex>. | # Инициализировать <tex>\mu_0, \sigma^2_0, t = 0</tex>. | ||
| - | # Принять | + | # Принять решение о метке пикселя на кадре ''t'': передний план тогда и только тогда, когда <tex>\frac{|(I_t-\mu_t)|}{\sigma_t} > k</tex>, где <tex>I_t</tex> — яркоcть пикселя на кадре ''t''. |
# Если пиксель отнесён к фону, обновить <tex>\mu_{t+1} = \rho I_{t+1} + (1 - \rho) \mu_ {t}</tex>, иначе <tex>\mu_{t+1} = \mu_t</tex>. | # Если пиксель отнесён к фону, обновить <tex>\mu_{t+1} = \rho I_{t+1} + (1 - \rho) \mu_ {t}</tex>, иначе <tex>\mu_{t+1} = \mu_t</tex>. | ||
# Если пиксель отнесён к фону, обновить <tex>\sigma^2_{t+1} = (I_{t+1}-\mu_{t+1})^ 2 \rho + (1 - \rho) \sigma ^ 2_ {t}</tex>, иначе <tex>\sigma ^ 2_{t+1} = \sigma ^ 2_t</tex>. | # Если пиксель отнесён к фону, обновить <tex>\sigma^2_{t+1} = (I_{t+1}-\mu_{t+1})^ 2 \rho + (1 - \rho) \sigma ^ 2_ {t}</tex>, иначе <tex>\sigma ^ 2_{t+1} = \sigma ^ 2_t</tex>. | ||
| Строка 50: | Строка 53: | ||
Протестируйте метод на последовательности pedestrians и повторите анализ из предыдущего пункта. Сделайте вывод о сравнении методов. | Протестируйте метод на последовательности pedestrians и повторите анализ из предыдущего пункта. Сделайте вывод о сравнении методов. | ||
| + | |||
| + | === Теперь в 3D! === | ||
| + | |||
| + | Предлагается изменить модель фона на более гибкую: трёхмерное нормальное распределение в цветовом пространстве RGB. Рассмотрите два варианта модели: с полной и с диагональной матрицей ковариаций. Оцените параметры на обучающей части (в оффлайн-режиме), не забывая о регуляризации матрицы ковариаций (можно добавлять положительное число к диагонали, например, 5). Решение о метке пикселя тестового кадра принимается сравнением плотности нормального распределения в данной точке с порогом. | ||
| + | |||
| + | Постройте ROC кривую для последовательности pedestrians, выберите значение порога и проанализируйте ошибки метода. Сделайте вывод о сравнении метода с остальными. | ||
| + | |||
| + | Повторите эксперимент, используя [https://en.wikipedia.org/wiki/HSL_and_HSV цветовое пространство HSV], в котором каналы коррелируют меньше. Для перевода изображения можно пользоваться встроенной функцией <code>rgb2hsv</code>. Обратите внимание, что она возвращает яркости на отрезке [0,1]. Сделайте вывод об уместности использования диагональной матрицы ковариаций для разных задач. | ||
| + | |||
| + | === Смесь гауссиан === | ||
| + | |||
| + | Смесь распределений может быть полезна для моделирования фона, если он нестатичен, например, содержит воду или листву, то есть, когда распределение может иметь несколько мод. | ||
| + | |||
| + | Поскольку разделение смеси гауссиан на реальных данных вычислительно затратно, предлагается сначала отладить алгоритм на синтетических данных. Сгенерируйте выборку из смеси гауссиан и попробуйте восстановить её параметры с помощью ЕМ-алгоритма. При этом нельзя пользоваться средствами разделения смеси распределений, входящими в MATLAB. Постойте график изменения логарифма правдоподобия, убедитесь в его монотонном росте. Приведите пример данных, в котором существенна зависимость от начального приближения, а также результаты запусков из разных начальных приближений. Уделите внимание оптимизации кода, используйте векторизацию. | ||
| + | |||
| + | Запустите алгоритм разделения смеси 3 трёхмерных гауссиан для вычитания фона в последовательности traffic, выбрав модель с учётом результатов предыдущего пункта (важны точность и скорость работы). При этом желательно использовать несколько случайных начальных приближений и выбирать лучшее по значению правдоподобия. Проанализируйте ошибки и сравните результат с использованием одной гауссианы, сделайте выводы. | ||
| + | |||
| + | == Дополнительная часть == | ||
| + | |||
| + | Приветствуется реализация и оценка модификаций приведённых моделей и алгоритмов. За интересные модификации начисляется до 1 бонусного балла (субъективно и безапелляционно). При этом учитываются критерии: | ||
| + | * оригинальность идеи (обратное количество студентов, кому она пришла в голову), | ||
| + | * мотивация (обоснование, почему метод должен работать лучше, и анализ применимости), | ||
| + | * хорошие результаты (повышение точности относительно базового метода и корректность протокола эксперимента). | ||
| + | |||
| + | == Материалы == | ||
| + | * [http://wordpress-jodoin.dmi.usherb.ca ChangeDetection.net] | ||
| + | * [https://en.wikipedia.org/wiki/Background_subtraction Wikipedia: Background subtraction] | ||
| + | * [[ЕМ-алгоритм, его модификации и обобщения]] | ||
| + | * [https://en.wikipedia.org/wiki/EM_algorithm Wikipedia: EM algorithm] | ||
| + | [[Категория:Учебные задачи]] | ||
Текущая версия
< Практикум на ЭВМ (317)/2013-2014
Срок сдачи задания — до 22 декабря 2013 г., 23:59. За день просрочки начисляется 0.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). Внимание! Пиксели с промежуточными метками (50, 85, 170) не входят в регион интереса и не участвуют в подсчёте точности. Другими словами, значения TP, FP, TN, FN не зависят от того, что вернул алгоритм на этих пикселях.
Можете воспользоваться готовыми функциями для подсвечивания маски переднего плана (highlightMask.m) и «проигрывания видео» (showvid.m), которые могут быть полезны для визуальной оценки качества: zip архив. Пример работы функции highlightMask:
Реализация
Одномерная гауссиана
В самом простом варианте можно моделировать распределение цвета в каждом пикселе одномерным нормальным распределением. Для этого нужно перевести видеопоследовательность в полутоновую. Это можно сделать, например, с помощью формулы из стандарта NTSC: . Для каждого пикселя обучающей части последовательности оцените параметры нормального распределения, используя яркости в каждой позиции пикселя (например, для pedestrians будет 299 точек для оценки плотности в каждом пикселе). Обратите внимание, что некоторые гауссианы получаются вырожденными. Для регуляризации разумно ограничивать возможное значение среднеквадратичного отклонения снизу. Можно использовать
. Далее, при классификации пикселя тестовой выборки, его нужно относить к фону тогда и только тогда, когда его яркость отклоняется от μ меньше, чем на kσ. Если установить k = 3, ожидается, что к переднему плану будут отнесены только 0.27% пикселей фона («правило 3σ»). Изменяя этот порог, можно регулировать соотношение между количеством ложноположительных и ложноортицательных обнаружений.
Реализуйте такую оценку фона и запустите на последовательности pedestrians. Проанализируйте качество вычитания фона с помощью трёх инструментов:
- Для каждого тестового кадра посчитайте количество ошибок 1 рода (FP) и 2 рода (FN). Постройте график зависимости ошибок от номера кадра. Какой эффект наблюдается?
- Проведите визуальную оценку. Для этого на каждом из кадров выделите области, отнесённые к переднему плану. Сделайте вывод о характере ошибок.
- Проведите оценку величин TPR и FPR (доли верноположительных и ложноположительных обнаружений, соответственно) для разных значений порога по всей тестовой последовательности (не усредняя по кадрам) и постройте графики ROC характеристики. Это будет необходимо для сравнения различных моделей.
Оценка гауссианы на лету
Если в последовательности присутствует дрейф фона, желательно оценивать его модель по нескольким последним кадрам. Проблема заключается в том, что строить новую модель для каждого кадра может быть вычислительно затратно, а также на предшествующих кадрах фон может быть загорожен объектами переднего плана. Чтобы этого избежать, можно оценивать модель в онлайн-режиме («на лету»).
Реализуйте следующий итеративный алгоритм оценки параметров гауссовской модели фона на лету (оценка также производится по полутоновым изображениям независимо для разных пикселей):
- Инициализировать
.
- Принять решение о метке пикселя на кадре t: передний план тогда и только тогда, когда
, где
— яркоcть пикселя на кадре t.
- Если пиксель отнесён к фону, обновить
, иначе
.
- Если пиксель отнесён к фону, обновить
, иначе
.
- Если не последний кадр, t += 1, перейти на шаг 2.
Новый параметр ρ отвечает за величину памяти метода (размер окна): чем меньше ρ, тем большее влияние имеют старые кадры. Рекомендуемые значения: ρ = 0.01, равен яркости на первом кадре,
. Не забывайте про регуляризацию: устанавливайте минимальное значение дисперсии.
Протестируйте метод на последовательности pedestrians и повторите анализ из предыдущего пункта. Сделайте вывод о сравнении методов.
Теперь в 3D!
Предлагается изменить модель фона на более гибкую: трёхмерное нормальное распределение в цветовом пространстве RGB. Рассмотрите два варианта модели: с полной и с диагональной матрицей ковариаций. Оцените параметры на обучающей части (в оффлайн-режиме), не забывая о регуляризации матрицы ковариаций (можно добавлять положительное число к диагонали, например, 5). Решение о метке пикселя тестового кадра принимается сравнением плотности нормального распределения в данной точке с порогом.
Постройте ROC кривую для последовательности pedestrians, выберите значение порога и проанализируйте ошибки метода. Сделайте вывод о сравнении метода с остальными.
Повторите эксперимент, используя цветовое пространство HSV, в котором каналы коррелируют меньше. Для перевода изображения можно пользоваться встроенной функцией rgb2hsv. Обратите внимание, что она возвращает яркости на отрезке [0,1]. Сделайте вывод об уместности использования диагональной матрицы ковариаций для разных задач.
Смесь гауссиан
Смесь распределений может быть полезна для моделирования фона, если он нестатичен, например, содержит воду или листву, то есть, когда распределение может иметь несколько мод.
Поскольку разделение смеси гауссиан на реальных данных вычислительно затратно, предлагается сначала отладить алгоритм на синтетических данных. Сгенерируйте выборку из смеси гауссиан и попробуйте восстановить её параметры с помощью ЕМ-алгоритма. При этом нельзя пользоваться средствами разделения смеси распределений, входящими в MATLAB. Постойте график изменения логарифма правдоподобия, убедитесь в его монотонном росте. Приведите пример данных, в котором существенна зависимость от начального приближения, а также результаты запусков из разных начальных приближений. Уделите внимание оптимизации кода, используйте векторизацию.
Запустите алгоритм разделения смеси 3 трёхмерных гауссиан для вычитания фона в последовательности traffic, выбрав модель с учётом результатов предыдущего пункта (важны точность и скорость работы). При этом желательно использовать несколько случайных начальных приближений и выбирать лучшее по значению правдоподобия. Проанализируйте ошибки и сравните результат с использованием одной гауссианы, сделайте выводы.
Дополнительная часть
Приветствуется реализация и оценка модификаций приведённых моделей и алгоритмов. За интересные модификации начисляется до 1 бонусного балла (субъективно и безапелляционно). При этом учитываются критерии:
- оригинальность идеи (обратное количество студентов, кому она пришла в голову),
- мотивация (обоснование, почему метод должен работать лучше, и анализ применимости),
- хорошие результаты (повышение точности относительно базового метода и корректность протокола эксперимента).
