Структурные методы анализа изображений и сигналов (курс лекций)/2011/Задание 1

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

Перейти к: навигация, поиск
Статья в настоящий момент дорабатывается.
Формулировка задания находится в стадии формирования. Просьба не приступать к выполнению задания, пока это предупреждение не будет удалено. Д.А. Кропотов 18:25, 26 марта 2011 (MSK)


Перейти к основной странице курса

Содержание


Начало выполнения задания: 28 марта 2011

Срок сдачи: 11 апреля 2011, 23:59

Задание состоит из двух вариантов. Распределение вариантов задания по студентам:

Вариант 1 Вариант 2
Ромов Петр, 202 Лямаев Сергей, 202
Иванов Петър, 202 Елшин Денис, 317
Некрасов Константин, 317 Новиков Павел, 317
Меркулова Татьяна, 317 Лобачева Екатерина, 209
Батанов Павел, 321 Птенцов Сергей, 321
Сапатов Александр, 321 Новикова Татьяна, 321
Шальнов Евгений, 321 Конев Артем, 321
Костин Григорий, 320 Икрам Магжан, 325
Переходько Евгения, 325 Парамонов Сергей, 324
Русланова Анна, 421 Ермишин Федор, 321
Исламгулов Ильдар, 420 Грядицкая Юлия, 411
Касперский Иван, 417 Тихонов Андрей, 417
Колев Денис, 417 Вартанов Сергей, 427
Ермаков Михаил, 427 Баранов Леонид, 428
Пироженко Александр, 428 Рябов Сергей, 428
Кузин Сергей, 528 Светличный Дмитрий, ВВО
Заякина Ольга, ВВО Беликов Владимир
Гребенкина Мария Субботин Никита

Для студентов, которых нет в этом списке, механизм выбора варианта следующий: первый вариант, если первая буква фамилии А–Л, второй — иначе.

Среда реализации для всех вариантов – MATLAB. Неэффективная реализация кода может негативно отразиться на оценке.

Вариант 1

Формулировка задания

Рассматривается классическая скрытая марковская модель (СММ) первого порядка, в которой полное правдоподобие задается как:

p(X,T|\theta)=p(t_1)\prod_{n=2}^Np(t_n |t_{n-1})\prod_{n=1}^Np(x_n |t_n )

Пусть скрытая компонента t_n в произвольный момент времени может принимать значения из множества \{1,\dots,K\}. Априорное распределение на значение скрытой компоненты в первый момент времени задается вектором w_1,\ldots,w_K, причем все w_i\ge 0 и \sum_iw_i=1. Распределение p(t_n |t_{n-1}) задается матрицей перехода A размера K\times K, где в ij-ой позиции стоит вероятность перехода из состояния i в состояние j. Все элементы этой матрицы неотрицательны и сумма элементов по каждой строке равна единице. Модель генерации данных задается нормальными распределениями со своими значениями вектора математического ожидания \mu_i и матрицы ковариации \Sigma_i для каждого состояния. Таким образом, набор параметров модели определяется вектором \vec{w}, матрицей A, значениями векторов математических ожиданий и матриц ковариаций для каждого состояния \{\mu_i,\Sigma_i\}_{i=1}^K.

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

Для выполнения задания необходимо:

  • Реализовать алгоритм генерации выборки из вероятностной модели СММ
  • Реализовать EM-алгоритм обучения СММ при заданном числе состояний K.
  • Реализовать алгоритм Витерби для сегментации сигнала при известных значениях параметров СММ
  • Протестировать реализованные алгоритмы на модельных сигналах
  • Рассчитать набор признаков для описания поведения мыши и на их основе найти 3 осмысленных поведенческих акта с помощью ЕМ-алгоритма обучения СММ, проинтерпретировать полученные поведенческие акты
  • Наложить полученные поведенческие акты на видео с поведением
  • Написать отчет в формате PDF с описанием всех проведенных исследований. Данный отчет должен, в частности, включать в себя графики сегментации модельных сигналов.

Спецификация реализуемых функций

Генерация выборки
[X, T] = HMM_GENERATE(N, w, A, Mu, Sigmas)
ВХОД
N — количество точек в генерируемой последовательности, uint32;
w — априорные вероятности для скрытых состояний, матрица типа double размера 1 x K;
A — матрица перехода, матрица типа double размера K x K;
Mu — центры гауссиан для каждого состояния, матрица типа double размера K x d, в которой в каждой строке стоит вектор мат.ожидания для соответствующего состояния;
Sigmas — матрицы ковариации гауссиан, массив типа double размера d x d x K, Sigmas(:,:,i) – матрица ковариации для i-ого состояния;
ВЫХОД
X — сгенерированная последовательность, матрица типа double размера N x d
T — последовательность скрытых состояний, матрица типа double размера 1 x N

Обратите внимание: в процедуре HMM_GENERATE количество признаков и количество скрытых состояний определяются неявно по размеру соответствующих элементов.

Сегментация
T = HMM_TEST(X, w, A, Mu, Sigmas)
ВХОД
X — входная последовательность, матрица типа double размера N x d, где N – количество точек в последовательности, d – количество признаков;
w — априорные вероятности, матрица типа double размера 1 x K, где K – количество скрытых состояний;
A — матрица перехода, матрица типа double размера K x K;
Mu — центры гауссиан для каждого состояния, матрица типа double размера K x d, в которой в каждой строке стоит вектор мат.ожидания для соответствующего состояния;
Sigmas — матрицы ковариации гауссиан, массив типа double размера d x d x K, Sigmas(:,:,i) – матрица ковариации для i-ого состояния;
ВЫХОД
T — полученная последовательность скрытых состояний, матрица типа double размера 1 x N

 

Обучение
[w, A, Mu, Sigmas, core] = HMM_EM_TRAIN(X, K)
[w, A, Mu, Sigmas, core] = HMM_EM_TRAIN(X, K, InputParameters)
ВХОД
X — входная последовательность, матрица типа double размера N x d, где N – количество точек в последовательности, d – число признаков;
K — количество скрытых состояний, число типа uint16;
InputParameters — (необязательный аргумент) набор дополнительных параметров, массив типа cell вида ParameterName1, ParameterValue1, ParameterName2, ParameterValue2 и т.д. Возможны следующие параметры:
  'w' — задаваемый пользователем вектор априорных вероятностей (соответственно, его не нужно определять в процессе EM-итераций);
  'A' — задаваемая пользователем матрица перехода;
  'Mu' — задаваемые пользователем центры гауссиан для каждого состояния;
  'Sigmas' — задаваемые пользователем матрицы ковариации гауссиан;
  'num_iter' — максимально допустимое число итераций EM-алгоритма (по умолчанию = 100);
  'tol_LH' — минимально допустимая величина отклонения по значению логарифма правдоподобия на одной итерации (по умолчанию = 10^{-2});
ВЫХОД
w — априорные вероятности для скрытых состояний, матрица типа double размера 1 x K;
A — матрица перехода, матрица типа double размера K x K;
Mu — центры гауссиан для каждого состояния, матрица типа double размера K x d, в которой в каждой строке стоит вектор мат.ожидания для соответствующего состояния;
Sigmas — матрицы ковариации гауссиан, массив типа double размера d x d x K, Sigmas(:,:,i) – матрица ковариации для i-ого состояния;
Core — все параметры для всех итераций EM-алгоритма, массив структур длины num_iter с полями 'w', 'A', 'Mu', 'Sigmas', 'gamma', 'LH', где gamma – матрица значений gamma для всех точек и всех состояний, LH – логарифм правдоподобия

Рекомендации по выполнению задания

Пример модельного сигнала для тестирования СММ
Пример модельного сигнала для тестирования СММ
  • При тестировании ЕМ-алгоритма обучения СММ рекомендуется убедиться в том, что значение неполного правдоподобия \log p(X|w,A,\mu,\Sigma) монотонно увеличивается в итерациях.
  • В качестве простейшего модельного сигнала для тестирования генерации, обучения и сегментации с помощью СММ можно взять одномерный сигнал с тремя состояниями, в котором два состояния хорошо отличимы друг от друга, а третье состояние является промежуточным. Например, в первом состоянии мат.ожидание = 0 и дисперсия маленькая (скажем, 0.1). Во втором состоянии мат.ожидание = 1 и такая же дисперсия, как и в первом состоянии. В третьем состоянии мат.ожидание = 0, а дисперсия в несколько раз больше (скажем, 0.5).
  • При тестировании генерации из модели СММ рекомендуется эксперимент с двухмерным сигналом, чтобы убедиться в корректности задаваемых корреляций
  • Для наложения поведенческих актов на видео рекомендуется следующая процедура:
    • Загрузить в MATLAB изображения с названиями поведенческих актов с помощью imread
    • Небольшими блоками загружать в MATLAB кадры видео с помощью aviread, накладывать на них картинки с названиями поведенческих актов и сохранять полученные кадры в виде отдельных JPG картинок на диск с помощью imwrite. Сохраненные картинки должны иметь название XXXXX.jpg, где XXXXX — номер кадра.
    • Собрать полученные картинки в видео-файл с помощью бесплатной программы VirtualDub. Для этого достаточно открыть первую картинку в программе (остальные загрузятся автоматически), установить частоту кадров 25fps, установить кодек (рекомендуется DivX) и сгенерировать AVI-файл.

Данные для выполнения задания

Видео-файл

MAT-файл, содержащий данные для каждого кадра видео. В нем находится массив структур, где каждая структура соответствует одному кадру, а поля структуры имеют следующее значение:

  • frame_number — номер кадра видео
  • centre — координаты центра масс мыши
  • nose — координаты предполагаемой точки носа мыши
  • tail — координаты предполагаемой точки основания хвоста мыши
  • contour — координаты точек контура мыши
  • dist_centre — расстояние от центра масс мыши до центра арены
  • dist_border — расстояние от центра масс мыши до ближайшей границы арены
  • eigen_features — проекции контура мыши на собственные контура, полученные с помощью метода главных компонент

Оформление задания

Выполненный вариант задания необходимо прислать письмом по адресу bayesml@gmail.com с темой «Задание 1. ФИО, номер группы». Убедительная просьба присылать выполненное задание только один раз с окончательным вариантом. Новые версии будут рассматриваться только в самом крайнем случае. Также убедительная просьба строго придерживаться заданной выше спецификации реализуемых функций. Очень трудно проверять большое количество заданий, если у каждого будет свой формат реализации.

Письмо должно содержать:

  • PDF-файл с описанием проведенных исследований
  • HMM_GENERATE.m
  • HMM_TEST.m
  • HMM_EM_TRAIN.m
  • Ссылка на видео-файл, размещенный на файлообменнике или на видео-хостинге, с наложенными поведенческими актами. Лучше вставить видео-файл непосредственно внутрь PDF-файла с отчетом (это можно сделать, например, в программе Adobe Acrobat 9 и выше). Тогда нужно прислать ссылку на этот PDF-файл.
  • Набор вспомогательных файлов при необходимости

Вариант 2

Формулировка задания

Рассматривается линейная динамическая система (ЛДС), в которой полное правдоподобие задается как:

p(X,T|\theta)=p(t_1)\prod_{n=2}^Np(t_n |t_{n-1})\prod_{n=1}^Np(x_n |t_n ),\\ p(t_n|t_{n-1})=\mathcal{N}(t_n|At_{n-1},\Gamma),\\ p(x_n|t_n)=\mathcal{N}(x_n|Ct_n,\Sigma),\\ p(t_1)=\mathcal{N}(t_1|\mu_0,V_0).

Все переменные модели являются непрерывными, т.е. t_n\in\mathbb{R}^D,\ x_n\in\mathbb{R}^d. Параметры модели A,\Gamma,V_0\in\mathbb{R}^{D\times D},\ C\in\mathbb{R}^{d\times D},\ \Sigma\in\mathbb{R}^{d\times d},\ \mu_0\in\mathbb{R}^D.

Данную ЛДС нужно использовать для решения задачи сопровождения (трекинга) объекта в пространстве. В частности, необходимо отфильтровать центр масс мыши на каждом кадре в видео-записи ее поведения в клетке.

Для выполнения задания необходимо:

  • Реализовать алгоритм генерации выборки из вероятностной модели ЛДС;
  • Реализовать алгоритм онлайн фильтрации сигнала с помощью фильтра Калмана;
  • Реализовать алгоритм уточнения фильтрации сигнала с помощью РТС уравнений;
  • Реализовать ЕМ-алгоритм обучения СММ при заданной размерности D. При этом часть параметров ЛДС также может быть задана пользователем;
  • Реализовать алгоритм генерации траектории движения абстрактного объекта в двухмерном пространстве. Способ генерации такой траектории отдается на выбор студента;
  • Протестировать реализованные алгоритмы на модельных данных;
  • Отфильтровать центр масс мыши в видео-сигнале с помощью реализованных алгоритмов. Выбор параметров фильтрации отдается на выбор студента. Способ выбора этих параметров необходимо отразить в отчете;
  • Наложить исходную траекторию центра масс мыши и отфильтрованную траекторию на видео с поведением;
  • Написать отчет в формате PDF с описанием всех проведенных исследований. Данный отчет должен, в частности, включать в себя графики фильтрации сгенерированных траекторий, а также графики фильтрации центра масс мыши в увеличенном разрешении.

Спецификация реализуемых функций

Генерация выборки
[X, T] = LDS_GENERATE(N, A, G, C, S, mu0, V0)
ВХОД
N — количество точек в генерируемой последовательности, uint32;
A — матрица преобразования среднего в последовательности t, матрица типа double размера D x D;
G — ковариационная матрица для распределения p(t_n|t_{n-1}), матрица типа double размера D x D;
C — матрица преобразования среднего при переходе от t_n к x_n, матрица типа double размера d x D;
S — ковариационная матрица для распределения p(x_n|t_n), матрица типа double размера d x d;
mu0 — мат.ожидание априорного распределения p(t_1), матрица типа double размера 1 x D;
V0 — ковариационная матрица априорного распределения p(t_1), матрица типа double размера D x D.
ВЫХОД
X — сгенерированная наблюдаемая последовательность, матрица типа double размера N x d
T — последовательность скрытых состояний, матрица типа double размера N x D

Обратите внимание: в процедуре LDS_GENERATE параметры D и d определяются неявно по размеру соответствующих элементов.

Фильтр Калмана и РТС уравнения
[Mus_back, Sigmas_back, Mus_fwd, Sigmas_fwd, LH, J] = LDS_forwardbackward(X, A, G, C, S, mu0, V0)
ВХОД
X — входная последовательность, матрица типа double размера N x d, где N – количество точек в последовательности, d – количество признаков;
A — матрица преобразования среднего в последовательности t, матрица типа double размера D x D;
G — ковариационная матрица для распределения p(t_n|t_{n-1}), матрица типа double размера D x D;
C — матрица преобразования среднего при переходе от t_n к x_n, матрица типа double размера d x D;
S — ковариационная матрица для распределения p(x_n|t_n), матрица типа double размера d x d;
mu0 — мат.ожидание априорного распределения p(t_1), матрица типа double размера 1 x D;
V0 — ковариационная матрица априорного распределения p(t_1), матрица типа double размера D x D.
ВЫХОД
Mus_back — мат. ожидания распределений p(t_n|X), матрица типа double размера N x D;
Sigmas_back — ковариационные матрицы распределений p(t_n|X), массив типа double размера D x D x N, где Sigmas(:,:,n) является матрицей ковариации для момента времени n;
Mus_fwd — мат. ожидания распределений p(t_n|x_1,\dots,x_n), матрица типа double размера N x D;
Sigmas_fwd — ковариационные матрицы распределений p(t_n|x_1,\dots,x_n), массив типа double размера D x D x N;
LH — логарифм неполного правдоподобия \log p(X|A,\Gamma,C,\Sigma,\mu_0,V_0), double;
J — матрицы J, массив типа double размера D x D x N-1;

 

Обучение
[A, G, C, S, mu0, V0] = LDS_EM_TRAIN(X, D, InputParameters)
ВХОД
X — входная последовательность, матрица типа double размера N x d, где N – количество точек в последовательности, d – число признаков;
D — размерность пространства скрытых состояний, число типа uint16;
InputParameters — (необязательный аргумент) набор дополнительных параметров, массив типа cell вида ParameterName1, ParameterValue1, ParameterName2, ParameterValue2 и т.д. Возможны следующие параметры:
  'A' — задаваемая пользователем матрица преобразования среднего в распределении p(t_n|t_{n-1})(соответственно, ее не нужно определять в процессе EM-итераций);
  'G' — задаваемая пользователем матрица ковариации p(t_n|t_{n-1});
  'C' — задаваемая пользователем матрица преобразования среднего в распределении p(x_n|t_n);
  'S' — задаваемая пользователем матрица ковариации в распределении p(x_n|t_n);
  'num_iter' — максимально допустимое число итераций EM-алгоритма (по умолчанию = 100);
  'tol_LH' — минимально допустимая величина отклонения по значению логарифма правдоподобия на одной итерации (по умолчанию = 10^{-2});
ВЫХОД
A — матрица преобразования среднего в последовательности t, матрица типа double размера D x D;
G — ковариационная матрица для распределения p(t_n|t_{n-1}), матрица типа double размера D x D;
C — матрица преобразования среднего при переходе от t_n к x_n, матрица типа double размера d x D;
S — ковариационная матрица для распределения p(x_n|t_n), матрица типа double размера d x d;
mu0 — мат.ожидание априорного распределения p(t_1), матрица типа double размера 1 x D;
V0 — ковариационная матрица априорного распределения p(t_1), матрица типа double размера D x D.

 

Генерация траектории
X = TRAJECTORY_GENERATE(N)
ВХОД
N — длина генерируемой траектории, uint32;
ВЫХОД
X — сгенерированная траектория движения объекта в двухмерном пространстве, матрица типа double размера N x 2;

Рекомендации по выполнению задания

  • При тестировании ЕМ-алгоритма обучения ЛДС рекомендуется убедиться в том, что значение неполного правдоподобия \log p(X|A,\Gamma,C,\Sigma,\mu_0,V_0) монотонно увеличивается в итерациях.
  • Простейшим способом генерации траектории объекта является генерация по скорости и ускорению, где ускорение иногда меняет величину и направление.
  • Один из вариантов тестирования реализованных алгоритмов на основе ЛДС следующий:
    • Сгенерировать траекторию движения объекта
    • Добавить к траектории случайный нормальный шум
    • Отфильтровать зашумленную траекторию с помощью фильтра Калмана; убедиться, что отфильтрованный сигнал ближе к истинной траектории, чем входной зашумленный сигнал.
    • Отфильтровать зашумленную траекторию с помощью РТС уравнений; убедиться, что результат является более точным по сравнению с фильтром Калмана.
  • При тестировании генерации из модели ЛДС рекомендуется эксперимент с двухмерным сигналом, чтобы убедиться в корректности задаваемых корреляций
  • Для наложения траектории движения на видео рекомендуется следующая процедура:
    • Загрузить в MATLAB изображения с названиями поведенческих актов с помощью imread
    • Небольшими блоками загружать в MATLAB кадры видео с помощью aviread, накладывать на них траекторию движения за последние 300 кадров и сохранять полученные кадры в виде отдельных JPG картинок на диск с помощью imwrite. Сохраненные картинки должны иметь название XXXXX.jpg, где XXXXX — номер кадра.
    • Собрать полученные картинки в видео-файл с помощью бесплатной программы VirtualDub. Для этого достаточно открыть первую картинку в программе (остальные загрузятся автоматически), установить частоту кадров 25fps, установить кодек (рекомендуется DivX) и сгенерировать AVI-файл.

Данные для выполнения задания

Видео-файл

MAT-файл, содержащий данные для каждого кадра видео. В нем находится массив структур, где каждая структура соответствует одному кадру, а поля структуры имеют следующее значение:

  • frame_number — номер кадра видео
  • centre — координаты центра масс мыши
  • nose — координаты предполагаемой точки носа мыши
  • tail — координаты предполагаемой точки основания хвоста мыши
  • contour — координаты точек контура мыши
  • dist_centre — расстояние от центра масс мыши до центра арены
  • dist_border — расстояние от центра масс мыши до ближайшей границы арены
  • eigen_features — проекции контура мыши на собственные контура, полученные с помощью метода главных компонент

Для фильтрации траектории движения мыши понадобятся только значения координат центра масс мыши.

RAR архив с процедурой для MatLab, которая строит пиксельное представление линии по координатам начала и конца линии.

Оформление задания

Выполненный вариант задания необходимо прислать письмом по адресу bayesml@gmail.com с темой «Задание 1. ФИО, номер группы». Убедительная просьба присылать выполненное задание только один раз с окончательным вариантом. Новые версии будут рассматриваться только в самом крайнем случае. Также убедительная просьба строго придерживаться заданной выше спецификации реализуемых функций. Очень трудно проверять большое количество заданий, если у каждого будет свой формат реализации.

Письмо должно содержать:

  • PDF-файл с описанием проведенных исследований
  • LDS_GENERATE.m
  • LDS_forwardbackward.m
  • LDS_EM_TRAIN.m
  • TRAJECTORY_GENERATE.m
  • Ссылка на видео-файл, размещенный на файлообменнике или на видео-хостинге, с наложенными исходной и фильтрованной траекториями движения центра масс мыши. Лучше вставить видео-файл непосредственно внутрь PDF-файла с отчетом (это можно сделать, например, в программе Adobe Acrobat 9 и выше). Тогда нужно прислать ссылку на этот PDF-файл.
  • Набор вспомогательных файлов при необходимости
Источник — «http://machinelearning.ru/wiki/index.php?title=%D0%A1%D1%82%D1%80%D1%83%D0%BA%D1%82%D1%83%D1%80%D0%BD%D1%8B%D0%B5_%D0%BC%D0%B5%D1%82%D0%BE%D0%B4%D1%8B_%D0%B0%D0%BD%D0%B0%D0%BB%D0%B8%D0%B7%D0%B0_%D0%B8%D0%B7%D0%BE%D0%B1%D1%80%D0%B0%D0%B6%D0%B5%D0%BD%D0%B8%D0%B9_%D0%B8_%D1%81%D0%B8%D0%B3%D0%BD%D0%B0%D0%BB%D0%BE%D0%B2_%28%D0%BA%D1%83%D1%80%D1%81_%D0%BB%D0%B5%D0%BA%D1%86%D0%B8%D0%B9%29/2011/%D0%97%D0%B0%D0%B4%D0%B0%D0%BD%D0%B8%D0%B5_1»
Личные инструменты