对PPT的简单总结省流版本，不代表全部内容。



# 运动估计

**Change Detection**:
- **方法**：使用图像减法（image subtraction）来检测场景中的变化。
- **应用**：广泛用于监控系统、交通监控等领域，通过比较时间序列图像来发现新的或消失的物体。

**Sparse Motion Estimation**:
- **方法**：使用模板匹配（template matching）来估计局部位移。
- **应用**：用于跟踪特定点或特征的运动，例如光流的计算、物体的跟踪等。模板匹配通过比较图像中的局部区域来找到最佳匹配位置。

**Dense Motion Estimation**:
- **方法**：使用光流（optical flow）来计算密集的运动向量场。
- **应用**：广泛用于视频压缩、运动分析、3D重建等领域。光流算法能够在整个图像范围内计算每个像素的运动，从而提供详细的运动信息。

## Change Detection

**检测移动物体**:
- **场景**: 在一个恒定背景中检测移动物体。
- **边缘移动**: 物体的前后边缘每帧仅移动几个像素。
  
**方法**:
- **图像减法**: 通过将当前帧 与上一帧相减，检测边缘变化。
- **结果**: 减法后的图像中，显著不同于零的像素就是物体的边缘。

这种方法在监控系统和交通监控中应用广泛，可以有效检测场景中出现的新物体或消失的物体。

## Sparse Motion Estimation

**稀疏运动估计**:

- **定义**: 通过识别在时间 $ t $ 和 $ t+\Delta t $ 拍摄的两幅图像中相对应的点对，计算稀疏运动场。
- **假设**: 兴趣点及其邻域的强度在时间上保持几乎不变。

**步骤**:
1. **检测兴趣点**: 在时间 $ t $ 检测图像中的兴趣点。
2. **搜索对应点**: 在时间 $ t+\Delta t $ 搜索这些兴趣点的对应点。

### 运动向量 Motion Vector

- **运动场**: 是二维数组的二维向量，表示3D场景点的运动。
- **图像中的运动向量**: 代表移动的3D点的图像位移。
  - **尾部**: 在时间 $ t $。
  - **头部**: 在时间 $ t+\Delta t $。
  - **瞬时速度估计**: 在时间 $ t $。

### 检测兴趣点 Detect Interesting Points

- **图像滤波器**:
  - Canny边缘检测器
  - Hessian脊检测器
  - Harris角点检测器
  - 尺度不变特征变换（SIFT）
  - 全卷积神经网络（FCN）

- **兴趣算子**:
  - 计算垂直、水平和对角方向的强度方差
  - 如果这些四个方差中的最小值超过阈值，则为兴趣点

## Dense Motion Estimation

**密集运动估计**:

- **假设**:
  - 在考虑的时间间隔内，物体的反射率和照明不变
  - 物体到相机和光源的距离在此时间间隔内没有显著变化
  - 时间 $t$ 时的小邻域 $ N_t(x,y) $ 在时间 $ t+\Delta t $ 时观测到的为某个偏移位置 $ N_{t+\Delta t}(x+\Delta x, y+\Delta y) $

- 这些假设在现实中可能并不完全成立，但提供了有用的计算和近似

密集运动估计主要用于计算整个图像的运动场，是光流计算的基础。尽管假设条件可能不完全准确，但它们仍然是估计运动的实用近似。

### Optical Flow Computation

**光流计算**:

- **光流方程**提供了一个可以应用于每个像素位置的约束
- 然而，这个方程没有唯一解，因此需要进一步的约束

例如，通过对一组相邻像素使用光流方程，并假设它们都有相同的速度，光流计算任务相当于使用最小二乘法解决一个线性方程组。

# 运动追踪 Motion Tracking

**跟踪方法**:

- **贝叶斯推理 Bayesian inference**:
  - 使用**概率模型**进行跟踪
- **卡尔曼滤波 Kalman filtering**:
  - 使用**线性模型假设**进行跟踪
- **粒子滤波 Particle filtering**:
  - 使用**非线性模型**进行跟踪


**主要步骤**:

- **预测** (Prediction):
   - 使用从时间 $i-1$ 之前的测量值 $(y_0, y_1, ..., y_{i-1})$来预测时间 $i$ 的状态。
   - 公式表示：$P(X_i | Y_0 = y_0, Y_1 = y_1, ..., Y_{i-1} = y_{i-1}) $

-  **关联** (Association):
   - 在时间 $i$ 选择与目标状态相关的测量值。

- **校正** (Correction):
   - 使用新的测量值 $y_i$ 来更新状态预测。
   - 公式表示：$ P(X_i | Y_0 = y_0, Y_1 = y_1, ..., Y_{i-1} = y_{i-1}, Y_i = y_i) $

## 贝叶斯推理 Bayesian inference

COMP9517 Week 9 精简

COMP9517 Week 7 精简

COMP9517 Final Exam Sample

问题传送门：https://leetcode.cn/problems/candy/description/




本题的思路是两次遍历。

注意到，核心规则为：

> 相邻的孩子中，评分高的孩子必须获得更多的糖果。

那么，我们将其拆分为左规则和右规则：

- 左规则：当 $ratings[i−1]<ratings[i]$ 时，$i$ 号学生的糖果数量将比 $i−1$ 号孩子的糖果数量多。
- 右规则：当 $ratings[i]>ratings[i+1]$ 时，$i$ 号学生的糖果数量将比 $i+1$ 号孩子的糖果数量多。

我们遍历该数组两次，处理出每一个学生分别满足左规则或右规则时，最少需要被分得的糖果数量。每个人最终分得的糖果数量即为这两个数量的最大值。

以左规则为例：我们从左到右遍历该数组，假设当前遍历到位置 $i$，如果有 $ratings[i−1]<ratings[i]$， 那么 $i$ 号学生的糖果数量将比 $i−1$ 号孩子的糖果数量多，我们令 $left[i]=left[i−1]+1$ 即可，否则我们令 $left[i]=1$。

```C++
class Solution {
public:
    int candy(vector<int>& ratings) {
        auto length = ratings.size();
        vector<int> left(length);
        for (auto i = 0; i < length; i++) {
            if (i > 0 && ratings[i - 1] < ratings[i]) {
                left[i] = left[i - 1] + 1;
            }
            else {
                left[i] = 1;
            }
        }

        vector<int> right(length);
        for (int i = length - 1; i >=0; i--) {
            if (i < length - 1 && ratings[i] > ratings[i + 1]) {
                right[i] = right[i + 1] + 1;
            }
            else {
                right[i] = 1;
            }
        }

        vector<int> result(length);
        auto sum = 0;
        for (int i = 0; i < length; i++) {
            result[i] = max(left[i], right[i]);
            sum += result[i];
        }
        return sum;
    }
};
```

但实际上用不着这么麻烦。主要在于向量right它不用做出来。它只是一个比较值，能拿来用就可以了。我们没必要存储它。向量result也是如此，如果我们只是为了求解一个sum，根本不需要把它存起来再一个个加上去。这种写法只是为了方便读者理解。

如果进行简化，可以将right直接简化成一个int类型，同时删去result相关的部分。

```C++
class Solution {
public:
    int candy(vector<int>& ratings) {
        auto length = ratings.size();
        vector<int> left(length);
        for (auto i = 0; i < length; i++) {
            if (i > 0 && ratings[i - 1] < ratings[i]) {
                left[i] = left[i - 1] + 1;
            }
            else {
                left[i] = 1;
            }
        }

        int right = 0;
        int sum = 0;
        for (int i = length - 1; i >=0; i--) {
            if (i < length - 1 && ratings[i] > ratings[i + 1]) {
                right += 1;
            }
            else {
                right = 1;
            }
            sum += max(left[i], right);
        }
        return sum;
    }
};
```