COMP9517 Week 4 Pattern Recognition Part 2

COMP9517 Week 4 Pattern Recognition Part 1

问题传送门：https://leetcode.cn/problems/gas-station/description/



常规思路是暴力解法，以每一个点作为起点检索，在路上如果某一个点的油箱容量为负，说明到不了， 直接break到下一个点，直到所有的点都被遍历过。**思路是没问题，就是会超时。**

```C++
class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int length = gas.size();
        vector<int> result(length, 0);
        for (int i = 0; i < length; i++) {
            for (int j = 0; j < length; j++) {
                int index = (i + j) % length;
                result[i] += gas[index] - cost[index];
                if (result[i] < 0) {
                    break;
                }
            }
            if (result[i] >= 0) {
                return i;
            }
        }
        return -1;
    }
};
```

换一种思维方式：

- 相关变量：`total_tank`。如果从0到n点，它所有的油箱总所得，和所有的油箱总支出的差值是负数，那么说明油量不能够支持完成环形遍历，需要返回-1。如果为正数，则一定存在符合条件的点。题目另外也规定了**该点只有一个**。
- 相关变量：`curr_tank`。这个值用于模拟当前油箱的剩余油量，当它小于0的时候，说明当前的点无法到达。
- 相关变量：`start_station`。这个值用于记录当前的起点，并与`i`进行运行模拟。

算法思想是：
1. 初始化各个值，将起点设定为0.
2. `total_tank`记录总的油量数据。
3. `curr_tank`用于记录从`start_station`到`i`的过程中，油箱油量的变化。如果它变为负数，则证明：从`start_station`到`i-1`中的这个区间内的任意一点，都不能到达点`i`。
> 原因很简单：从`start_station`到它的下一站，是有可能有大于0的余油的；但是如果从`start_station+1`开始往`i`走，那么起始油量一定是0。有余油都跑不到`i`，更别提从0开始了。所以中间的所有点会被直接忽略掉。
4. 再次将起始点`start_station`记录为`i+1`，并将`curr_tank`置空，以重新模拟。
5. 最终判定，如果`total_tank`不为负数，说明存在点能够完成，并且最后一定是`start_station`符合条件。如果为负数，返回`-1`。

```C++
class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int total_tank = 0;
        int curr_tank = 0;
        int start_station = 0;
        
        for (int i = 0; i < gas.size(); i++) {
            total_tank += gas[i] - cost[i];
            curr_tank += gas[i] - cost[i];
            if (curr_tank < 0) {
                // Set Next Station as Start
                // Reset tank info
                start_station = i + 1;
                curr_tank = 0;
            }
        }
        
        return total_tank >= 0 ? start_station : -1;
    }
};
```

Leetcode 134. 加油站

Shape features (Part 2)
- Basic shape features
- Shape context
- Histogram of oriented gradients (HOG)



# 特征编码 Feature Encoding
**特征编码**：
- **本地SIFT特征的全局编码**：
  - 将图像的本地SIFT关键点描述符组合成一个全局向量

**图解说明**：
- 图像I中选取若干个位置的图像块（如位置i和位置j）。
- 提取每个图像块的本地特征（如SIFT关键点描述符）。
- 将这些本地特征组合，形成图像I的全局表示$\Phi(I)$。
        
    ![image.png](/static/img/03360f91c6f9ced28abcc69107e1e048.image.png)

- **最流行的方法：词袋模型（BoW）**：
  - 本地图像特征的数量可变
  - 编码成固定维度的直方图

**流程图解**：

1. **训练阶段**：
   - **训练集**：
     - 从训练集中提取SIFT特征。
     - 对特征进行采样和聚类，生成词汇（Vocabulary）。
     - 构建训练集的直方图。
     - 使用SVM（支持向量机）训练模型（分类器）。

2. **测试阶段**：
   - **测试集**：
     - 从测试集中提取SIFT特征。
     - 使用训练阶段生成的词汇构建测试集的直方图。
     - 使用训练好的分类器对直方图进行分类，生成标签。

![image.png](/static/img/4c107fc55024bfd4b075a924e91e7219.image.png)

这种方法通过将本地特征编码成固定维度的直方图，能够有效地处理图像分类和检索等任务。


# 形状特征 Shape Features

- **形状**是物体的一个基本特征。
- 形状特征通常在图像分割之后提取。
- 它们可以用于识别和分类物体。

**定义形状特征的挑战**：

- **对刚性变换不变**：
  - 形状特征应当对旋转、缩放和平移等刚性变换保持不变。
  
- **容忍非刚性变形**：
  - 形状特征应当能够容忍某些非刚性变形，例如弯曲和拉伸等。

- **未知的对应关系**：
  - 形状特征之间可能没有明确的对应关系，这增加了匹配和识别的难度。

![image.png](/static/img/1a8b358abd7bc1271dd140519ee60aa6.image.png)

## 形状特征基础 Basic Shape Features

### **一些简单的几何形状描述符**：

1. **净面积 (Net Area)**：
   - 形状的实际面积。

2. **主轴 (Principal Axes)**：
   - 包括长轴 (Major Axis) 和短轴 (Minor Axis)。
   - 形状的长轴是通过形状的最长直径定义的，而短轴则是垂直于长轴的最短直径。

3. **凸面积 (Convex Area)**：
   - 包围该形状的凸包的面积。
   - 凸包是指能够完全包围形状的最小凸多边形。

![image.png](/static/img/a510544023d48483c642c54ba32de1dd.image.png)

### **凸性和凹性的基本概念**：

**物体的凸性与凹性 (Convexity versus Concavity of an Object)**：
   - 当物体的任意两点之间的直线完全包含在物体内部时，该物体被称为凸 (Convex)。
   - 如果存在两点之间的直线部分不在物体内部，则该物体被称为凹 (Concave)。

**物体的凸包 (Convex Hull of an Object)**：
   - 包含该物体的最小凸集合。
   - 凸包是指能够完全包围形状的最小凸多边形。

**物体的凸缺陷 (Convex Deficiency of an Object)**：
   - 凸包与物体之间的差集。
   - 这是指从凸包中去掉原物体所剩下的部分。

![image.png](/static/img/474f0e09b545c5d5cce11f1a5a80394d.image.png)

### **物体的形状特征**：

1. **紧致度 (Compactness)**：
   - 公式：$ \text{Compactness} = \frac{\text{Area of the object}}{\text{Area of a circle with the same perimeter}} $
   - 描述物体的面积与具有相同周长的圆的面积的比值。

2. **圆度 (Circularity)**：
   - 公式：$ \text{Circularity} = \frac{4\pi \times \text{Area of the object}}{\text{Perimeter}^2} $
   - 描述物体的面积乘以 $4\pi$ 后与其周长的平方的比值。
   - 对于圆形来说，这个比值为1。

![image.png](/static/img/961e2f0c420d10a196f82c3cc5fd797e.image.png)

3. **延伸度 (Elongation)**：
   - 公式：延伸度 = 物体包围盒的长度与宽度之比
   - 描述物体的包围盒（即最小外接矩形）的长度和宽度的比值，用于衡量物体的细长程度。

4. **偏心率 (Eccentricity)**：
   - 公式：偏心率 = 短轴长度与长轴长度之比
   - 描述物体的短轴（minor axis）长度与长轴（major axis）长度的比值，用于衡量物体形状的扁平程度。

![image.png](/static/img/6b19e4874f4bb9672dacc67a51bef478.image.png)

## 轮廓描述符 Boundary Descriptors

### **链码描述符（Chain code descriptor）**：

1. **链码描述符的定义**：
   - 通过连续边界点的相对位置表示物体形状。
   - 由一个从起始点开始的方向列表组成。
   - 提供了一个紧凑的边界表示。

2. **示例**：
   - 给出了一个示例，其中边界按照特定的方向编码成链码。
   - 例子中的链码为：6, 7, 0, 1, 1, 0, 7, 7。

![image.png](/static/img/718de536cbd43873a7d69c554a362c3b.image.png)

### **局部曲率描述符（Local curvature descriptor）**：

1. **定义**：
   - 物体的曲率是局部形状特征。
   - 凸（相对于凹）部分具有正（相对于负）曲率。

2. **图示**：
   - 图中展示了一个物体的形状和对应的曲率图。
   - 曲率图显示了曲率 $\kappa$ 随着路径 $s$ 的变化，其中凸部分对应正曲率，凹部分对应负曲率。

![image.png](/static/img/c6a117e1263d6cd686b4e56917616aa0.image.png)

这张幻灯片展示了局部曲率的两种解释：

1. **几何解释（Geometrical interpretation）**：
   - 曲率 $\kappa(s)$ 可以表示为曲率半径 $r(s)$ 的倒数：$\kappa(s) = \pm \frac{1}{r(s)}$。
   - 在几何解释中，曲线的内部对应正曲率，外部对应负曲率。

2. **物理解释（Physical interpretation）**：
   - 曲率 $\kappa(s)$ 可以表示为切线向量 $\tau(s)$ 随弧长 $s$ 的变化率：$\kappa(s) = \pm \left\| \frac{d\tau(s)}{ds} \right\|$。
   - 物理解释中，通过计算切线向量变化率来确定曲率。

![image.png](/static/img/ed60c6bd37a06355b147b6e8e72ed582.image.png)

### **全局曲率描述符（Global Curvature Descriptors）**：

1. **总弯曲能量（Total bending energy）**：
   - 公式：$ B = \oint_C \kappa^2(s) \, ds $
   - 描述：表示将杆弯曲成该轮廓所需的物理能量。
   - 特点：圆形物体具有最小的轮廓弯曲能量，$ B = 2\pi / r $。

2. **总绝对曲率（Total absolute curvature）**：
   - 公式：$ K = \oint_C |\kappa(s)| \, ds $
   - 描述：物体轮廓沿曲线的曲率绝对值的积分。
   - 特点：凸物体具有最小的总绝对曲率，$ K = 2\pi $。

这两个全局曲率描述符帮助我们量化和比较不同形状的整体弯曲程度和曲率特性。

### **径向距离描述符**（Radial distance descriptor）：

- **计算方法**：
  - 使用形状的质心 $ C $ 作为参考点，计算其边界上所有 $ N $ 个像素 $ i$  到质心的径向距离 $ d $。
  - 通过将 $ d(i) $ 正规化为最大距离来实现尺度不变性，得到径向距离 $ r(i) $。

- **应用**：
  - 信号 $ r(i) $ 穿过其均值的次数可以用作边界粗糙度的度量。

径向距离描述符通过分析形状边界上各点到质心的距离，帮助我们理解和量化形状的边界特性。

![image.png](/static/img/976abab2e44cccb23977a6ece455fc16.image.png)

## 形状特征的应用举例

- **结合特征描述符来分类对象**：
  - 通过结合不同的特征描述符（如面积和圆形度），可以对对象进行分类。
  - 幻灯片左侧的图像展示了红色和绿色的不同形状对象。
  - 右侧的散点图用面积和圆形度两个特征来表示这些对象。通过在图中标记不同对象的位置，可以根据这些特征对它们进行分类。
  - 例如，绿色区域表示某些特定特征的对象，其他对象则根据它们的特征值分布在图的不同位置。

这种方法利用多个特征来进行对象的识别和分类，提供了一种直观而有效的形状分析手段。

![image.png](/static/img/395876f068ccb97abe45e748b3931f06.image.png)

# 形状上下文（Shape Context）

是一种基于点的局部特征描述符。

- 从形状的轮廓上选择 $ n $ 个点 $ p_i $。
- 对于每个点，制作一个相对坐标直方图 $ h_i $，包含其他 $ n-1 $ 个点的相对坐标。
- 这就是点 $ p_i $ 的形状上下文。

![image.png](/static/img/06bd050167b92b1b18217fab6d1d8ff6.image.png)

## 形状匹配 Shape Matching

### 步骤1

在形状边缘上采样一系列点。举例来说，可以使用Canny边缘检测器来完成这一任务。

**步骤包括：**
1. **高斯滤波（Gaussian filtering）**：平滑图像以减少噪声。
2. **强度梯度（Intensity gradient）**：计算图像中像素点的梯度强度和方向。
3. **非极大值抑制（Non-maximum suppression）**：细化边缘，保留梯度幅值最大的像素点。
4. **滞后阈值处理（Hysteresis thresholding）**：使用双阈值方法确定强边缘和弱边缘，并连接边缘。
5. **边缘跟踪（Edge tracking）**：通过连接强边缘像素和弱边缘像素，追踪完整的边缘。

通过这些步骤，可以在图像中提取出清晰的边缘，这些边缘上的点可以用于后续的形状匹配过程。

这张幻灯片介绍了形状匹配的第二步和第三步。

### 步骤2

计算每个点的形状上下文。

$$
h_i(k) = \#\{q \neq p_i : (q - p_i) \in \text{bin}(k)\}
$$

这意味着对于每个点 $ p_i $，计算其他 $ n - 1 $ 个点相对于 $ p_i $ 的坐标，并将其放入一个直方图 $ h_i $ 中。

### 步骤3

计算两个形状 $ P $ 和 $ Q $ 之间的代价矩阵。

$$
c_s(p, q) = \frac{1}{2} \sum_{k=1}^{K} \frac{[g(k) - h(k)]^2}{g(k) + h(k)}
$$

其中，$ g $ 是形状 $ P$ 中点 $ p $ 的形状上下文，$h$ 是形状 $ Q $ 中点 $ q$ 的形状上下文。

这一步的目的是通过计算形状上下文之间的差异来衡量两个形状之间的相似性。代价矩阵 $ c_s(p, q) $ 表示了形状 $ P $ 和形状 $ Q $ 之间的匹配代价。


![image.png](/static/img/341e2cab606d96a86cd3e9cafb6a29ab.image.png)


### 步骤4

**第四步：找到使点对之间总成本最小的一对一匹配**

$$
H(\pi) = \sum_{i} c_s(p_i, q_{\pi(i)}) 
$$

这意味着通过最小化形状 $ P $ 和 $ Q$ 之间的匹配代价 $ c_s(p_i, q_{\pi(i)}) $，找到点之间的一对一匹配。

### 步骤5

**第五步：基于一对一的点匹配将一个形状转换为另一个形状**
- 选择所需的变换（例如仿射变换）
- 应用最小二乘法或 RANSAC 拟合
- 这将产生最优变换 $$ T $$

这一步的目的是根据第四步中的匹配结果，将一个形状通过所选的变换方法转换为另一个形状，从而使它们尽可能地对齐。




# 方向梯度直方图 Histogram of Oriented Gradients，HOG

- HOG 描述了在局部区域内梯度方向的分布。
- HOG 不需要初始分割，这意味着它可以直接在整个图像上计算，而不需要先进行图像的分割处理。

HOG 特征主要用于对象检测等任务，通过捕捉图像中局部梯度方向的分布来表征图像的纹理和形状信息。

![image.png](/static/img/86e7949d6e7e74f6dc2833332d17a2d7.image.png)

## 处理步骤

**步骤 1：计算每个像素点的梯度向量**
- 梯度幅度：表示梯度的强度。
- 梯度方向：表示梯度的方向。

在输入图像中，每个像素点的梯度向量是通过计算其梯度幅度和梯度方向得到的。这些梯度信息可以用来表示图像中局部区域的变化，帮助捕捉图像的边缘和纹理特征。

![image.png](/static/img/e708f651ba8b717e30907cea41c54829.image.png)

**步骤 2：构建单元格内所有像素的梯度直方图**

- 将方向划分为 $ N $ 个箱（通常 $ N = 9 $ 个箱，将 180 度平均分割）。
- 将每个像素的梯度幅度分配到对应其方向的箱中。

在输入图像中，每个单元格中的像素梯度方向会被分配到不同的箱中，形成一个梯度直方图。这个直方图反映了该单元格内不同方向梯度的分布情况，有助于描述图像的局部特征。

![image.png](/static/img/2683570c6a6358f416d60793cc123044.image.png)

**步骤 3：生成检测窗口级别的 HOG 描述符**

- 连接单元格直方图
- 对单元格直方图进行块归一化

具体过程如下：

1. 将每个单元格的梯度直方图连接起来，形成一个长的特征向量。
2. 将这些特征向量进行归一化处理，以减少光照和对比度变化的影响。

在这张幻灯片中，以一个 $7 \times 15$ 的检测窗口为例，每个单元格的尺寸为 $8 \times 8$ 像素，每个块包含 $2 \times 2$ 个单元格。特征计算如下：
- 每个单元格有 9 个方向箱（orientation bins）。
- 总共有 $7 \times 15$ 个块，每个块包含 4 个单元格。
- 因此，总特征数为 $(7 \times 15) \times 9 \times 4 = 3,780$。

这一步生成的检测窗口级别的 HOG 描述符可以用于对象检测和识别任务中。

![image.png](/static/img/58cea0ea36071a22f75f92ea44dcd0f7.image.png)

![image.png](/static/img/9acdfadab92843b2eb7aca5b67cc248d.image.png)

## HOG操作

**通过滑动窗口在图像上进行检测**

1. **检测窗口 (Detection Window)**：在图像上定义一个固定大小的检测窗口，这里使用的是 $7 \times 15$ 块的窗口。
2. **块 (Block)**：每个块包含 $2 \times 2$ 个单元格，每个单元格的大小为 $8 \times 8$ 像素。
3. **滑动窗口 (Sliding Window)**：将检测窗口在图像上滑动，以不同的位置提取特征。每次滑动的步长通常是一个单元格的宽度。

通过在图像上滑动窗口，可以在不同的位置提取特征直方图，从而进行对象检测。这种方法可以确保整个图像区域都被检测到，适用于检测多种不同大小和位置的目标对象。

![image.png](/static/img/f91706f87730952f5e5ed485fc06c19f.image.png)


1. **计算HOG描述符**：从训练数据集中计算许多示例窗口的HOG描述符。
2. **手动标记**：将每个示例窗口手动标记为“person”或“background”。
3. **训练分类器**：从这些示例窗口及其标签中训练一个分类器（如SVM）。
4. **预测标签**：对于每个新的（测试）图像，使用该分类器预测每个窗口的标签。

通过这种方法，可以使用训练好的分类器对新图像进行对象检测，识别出图像中的人物或背景。

![image.png](/static/img/0a160c53d7d0549978b4c384e70b13c4.image.png)

## HOG 应用举例

**图像中检测人像**

![image.png](/static/img/f77803bdb6d1d65e0d6e7d4ce341a187.image.png)

**在视频中检测并追踪人像**

![image.png](/static/img/63615825b83e84a937dea233cc0991d1.image.png)

**使用可变形零件模型进行细粒度检测（Fine-grained detection using deformable parts model）**

![image.png](/static/img/a7c0a1f94d4e74f7e42db5a199e60c60.image.png)

# 例题

Given the image on the right showing the result of a segmentation of various objects and the desired classification of these objects. The two different colours (red and green) indicate the two different classes which the objects are to be assigned to. A straightforward way to perform classification is by computing the value of a quantitative shape measure for each object and then thresholding those values. Suppose we compute the circularity and the eccentricity. Which of these two measures can be used to produce the shown classification?

![image.png](/static/img/df78e8a54681880e7233d42103757852.image.png)

A. Only circularity

B. Only eccentricity

C. Both circularity and eccentricity

D. Neither circularity nor eccentricity


:::info{title="相关信息"}
根据图片中的对象，红色对象是接近圆形的，而绿色对象则是更细长和弯曲的。这表明我们可以利用对象的形状特征来进行分类。

圆形度（circularity）是用于描述一个对象接近圆形的程度，所以红色对象会有较高的圆形度，而绿色对象的圆形度较低。

偏心率（eccentricity）是用于描述一个对象的细长程度，细长的对象会有较高的偏心率，而接近圆形的对象偏心率较低。

因此，基于圆形度和偏心率的组合可以将这些对象正确分类为红色和绿色对象。

所以，正确答案是：

C. Both circularity and eccentricity
:::

Pattern recognition concepts

Supervised learning for classification