OMSCS-CV课程笔记14-Action Recognition

这个系列是Gatech OMSCS 计算机视觉课程(CS 6476: Computer Vision)的同步课程笔记。课程内容涉及图像处理以及传统计算机视觉的相关理论和方法，本节主要介绍视频分析和动作识别的相关内容。

Video Analysis

Background Subtraction

在视频分析中我们把图像序列看成是一个三维的数组 $I (x, y, t)$ ，通过视频分析我们可以从图像序列中识别出运动的物体。视频分析的一个经典应用是背景差分(background subtraction)，我们可以从视频中对背景图像进行建模并通过差分的方式来获得前景图像：

背景差分在交通摄像头监控、行为识别、目标跟踪等很多领域都有相关的应用，它的基本流程如下：

估计 $t$ 时刻的背景图像；
将当前图像与背景图像相减，得到差分图像；
对差分图像进行阈值化，得到前景图像的掩码。

显然背景差分最重要的一步是对背景图像进行建模，最简单的方式是使用前一帧的图像作为背景：

B (x, y, t) = I (x, y, t - 1)

然而这种方法容易收到运动物体的外观、速度等因素的影响，因此实际中基本不会直接使用之前的图像作为背景。比较常用的背景建模方式是使用均值或者中值图像，通过前 $n$ 帧的图像进行均值滤波或是中值滤波来获得背景：

B (x, y, t) = \frac{1}{n} \sum_{i = 1}^{n} I (x, y, t - i)

B (x, y, t) = median {I (x, y, t - i)}

背景差分算法的优势在于实现简单、运行效率高、同时对于可变的背景具有一定的适应性；但它的缺陷在于算法的效果容易收到物体运动速度以及视频帧率的影响，而且中值滤波需要存储之前的图像对内存有更高的要求，同时阈值如何设置需要进行不断的调试才能确定。

Epipolar Plane Images

本节课还介绍了另一种有趣的视频分析应用，称为极几何图像(epipolar plane images)。假设物体不动，相机沿直线运动，则空间点 $P$ 会位于同一条极线上：

我们可以把这些图片叠到一起，可以得到图像的长方体：

如果从Y轴进行切片则可以发现空间中同一个点在切片上会变成一条直线，而这条直线的斜率则对应了该点的深度。

类似地，我们同样可以对运动的物体构造极几何图像。此时运动的物体会在切片图像上留下特定的图案，一些研究表明我们可以利用这种图案来进行动作的识别。

Activity Recognition

Human Activity in Video

对视频中人的行为进行识别是比较困难的任务，一般来说没有一个通用的解决方法。常用的方法包括对单帧图像进行识别或是结合一些运动的信息进行识别等。从算法层面来讲进行行为识别可以分为基于模型的动作识别(model based action recognition)以及基于模型的行为识别(model based activity recognition)两种：动作识别是对人体的不同部位以及姿态进行识别，而行为识别则是在动作的基础上根据模型来识别人的行为

目前行为识别主流方式是通过结合时空的模式来进行分析。一般来说这类方法不需要显式地对人体进行跟踪，只需要从视频中提取物体的运动模式并训练一个分类器即可。

Motion History Images

要进行行为识别就需要将物体的运动记录下来，一种经典的处理方法是使用运动历史图(motion history image, MHI)来保存运动信息。MHI通过对图像中的像素进行更新来记录物体的运动信息：

I_{τ} (x, y, t) = {\begin{aligned} τ, & if moving \\ max {I_{τ} (x, y, t - 1), 0}, & otherwise \end{aligned}

在MHI的基础上进行阈值化就可以得到运动能量图(motion energy image, MEI)，MEI和MHI共同组成了运动在时空上的模板：

对于视频中运动的物体我们利用这种时空上的模板进行模板匹配从而实现简单的行为识别：

Image Moments

除了直接使用模板外我们还可以利用模板的统计特征来训练分类器从而实现行为识别。最简单的图像特征是矩(moment)，它定义为：

M_{i j} = \sum_{x} \sum_{y} x^{i} y^{j} I (x, y)

类似地，可以定义图像的中心矩(central moments)为：

μ_{p q} = \sum_{x} \sum_{y} (x - \bar{x})^{p} (y - \bar{y})^{q} I (x, y)

\bar{x} = \frac{M_{10}}{M_{00}}, \bar{y} = \frac{M_{01}}{M_{00}}

中心矩是一个平移不变量，同样的形状无论发生什么样的平移它的中心矩保持不变。实践中更常用的图像矩特征是Hu矩(Hu moment)，它是一个包含7个矩的特征，而且具有平移和尺度不变性。Hu矩的定义如下：

有了特征后就可以利用各种机器学习模型来完成行为的识别，主要流程如下：

Hidden Markov Models

Markov Models

本节课最后介绍了隐马尔科夫模型(hidden Markov model, HMM)在行为识别中的应用。在正式介绍HMM前首先需要引入马尔科夫模型的概念，简单来说马尔科夫模型是满足一阶马尔科夫性的模型，它由3部分组成：

状态(state)： ${S_{1}, S_{2}, . . ., S_{n}}$
状态转移概率(state transition probabilities)： $a_{i j} = P (q_{t + 1} = S_{i} | q_{t} = S_{j})$
初始状态分布(Initial state distribution:)： $π_{i} = P (q_{1} = S_{i})$

在马尔科夫模型的基础上，HMM中指系统状态不可见但是我们可以对系统进行观测，系统状态到观测结果的过程由发射概率(emission probabilities)控制：

b_{j} (k) = P (o_{t} = k | q_{t} = S_{j})

因此，HMM可以看做是由状态转移、发射概率以及初始状态分布构成的三元组 $λ = (A, B, π)$ 。

3 Computational Problems of HMMs

HMM可以求解三种问题：

Evaluation：给定模型 $λ = (A, B, π)$ ，计算观测序列 $O = {o_{1}, o_{2}, . . ., o_{T}}$ 的概率；
Decoding：给定模型 $λ = (A, B, π)$ 和观测序列 $O = {o_{1}, o_{2}, . . ., o_{T}}$ ，计算产生该观测序列最有可能的状态序列；
Learning：给定观测序列 $O = {o_{1}, o_{2}, . . ., o_{T}}$ ，学习产生该序列最有可能的模型 $λ = (A, B, π)$ 。

以上问题都有非常经典的求解方法，本节课中只介绍了evaluation的求解过程。evalution可以形式化为计算如下定义的概率：

P (O | λ) = \sum_{q} P (O | q, λ) P (q | λ)

其中，

P (O | q, λ) = \prod_{t} P (o_{t} | q_{t}, λ) = b_{q_{1}} (o_{1}) b_{q_{2}} (o_{2}) . . . b_{q_{T}} (o_{T})

P (q | λ) = π_{q_{1}} a_{q_{1} q_{2}} a_{q_{2} q_{3}} . . . a_{q_{T - 1} q_{T}}

因此直接求解的方法是对所有可能的状态序列 ${q_{1}, q_{2}, . . ., q_{T}}$ 进行求和。然而这种直接求解的计算复杂度为 $O (T N^{T})$ ，在实际计算中是不可行的。

实际中解决evaluation问题使用的是前后向算法，它分为前向计算和后向计算两个步骤。前向计算通过递归的方式来计算前向概率 $α_{t}$ ：

α_{t} (i) = P (o_{1}, . . ., o_{t}, q_{t} = i | λ)

它表示到 $t$ 时刻为止观测到 ${o_{1}, . . ., o_{t}}$ 且状态为 $q_{t} = i$ 的概率，它可以通过递归的方式来求解：

α_{t + 1} (j) = [\sum_{i = 1}^{N} α_{t} (i) a_{i j}] b_{j} (o_{t + 1})

当递推到 $T$ 时刻时， $P (O | λ)$ 可通过对前向概率求和来计算：

P (O | λ) = \sum_{i = 1}^{N} α_{T} (i)

使用前向概率递推计算的复杂度为 $O (N^{2} T)$ ，远低于直接计算的复杂度。类似地，我们可以定义后向概率为：

β_{t} (i) = P (o_{t + 1}, o_{t + 2}, . . ., o_{T} | q_{t} = i, λ)

递推时首先初始化：

β_{T} (i) = 1

然后从后向前递推：

β_{t} (i) = \sum_{i = 1}^{N} a_{i j} b_{j} (o_{t + 1}) β_{t + 1} (j)

当递推到 $t = 1$ 时刻只需要再求和即可：

P (O | λ) = \sum_{i = 1}^{N} π_{i} b_{1} (o_{1}) β_{1} (i)

Reference

Wikipedia: Hidden Markov model
第10章：隐马尔科夫模型，统计学习方法（第2版）