Manifold-Based Visual Object Counting

一、基于流形的视觉目标计数

1. 提出了一种基于流形的视觉目标计数方法；
2. 通过正则化和非线性映射来考虑非负性和稀疏表示，来优化局部几何的特征；
3. 用局部模式学习和分层搜索被用来进一步提高所提出的方法及其变体的计算效率。

二、方法概括

figure1 提出的基于流形的视觉对象计数方法。橙色框内为测试部分（step 4）。红色为训练部分（step 1-3）。

1. 基于训练样本的点标注生成密度图作为groundtruth，并从中训练图像中提取图像patch,从密度图中提取密度patch；
2. 对提取的patch集进行特征工程；
3. 对patch集做聚类，并生成层级架构；
4. 对patch集作密度图重构，目标为得到最优权重，以生成测试集的密度图。

三、方法详细流程

1. 生成训练集的密度图

figure2. 行人点标注和对应的密度图

• 密度图可以用2D高斯核函数计算： $$\pmb{I}_d^i(z) = \sum_{U\in{\pmb{U}^i}}\mathcal{N}(z; U,\sigma^2\pmb{1}_{2\times2})$$ 其中$\pmb{I}_d$是$\pmb{I}$的密度图，即ground truth，$z$ 是图像 $\pmb{I}^i$ 的像素索引，$i$是图像索引， $U$ 是标注的点的坐标，$\pmb{U}^i$ 是 $\pmb{I}^i$ 中所有点的坐标集。$\mathcal{N}$是归一化2D高斯核函数，$\sigma^2$ 是用于平滑局部分布的 $\mathcal{N}$ 的方差，并且根据对象的大小(大约是对象大小的1/2)来设置。
• 而目标计数可以计算为密度图上所有点之和： $$\pmb{I}_d^i(z) = \sum_{z\in{\pmb{I}_d^i}} \pmb{I}_d^i(z)$$

2. 特征工程

• 为了增加特征空间中的采样密度和减少计算负担，采用主成分分析法（PCA） 对patch形式的原始数据特征进行集中、归一化和降维。

3. 构建搜索架构

• 为了降低算法的时间复杂度，采用分层搜索结构，该结构的节点是通过聚类产生的。
• 结构分为两层，第一层包含$\sqrt{K}$个节点，代表图像patch集$\pmb{Y}$用K-means生成的$\sqrt{K}$个聚类的质心，第二层中，第一层的每个节点包含$\sqrt{K}$个子节点，代表$\pmb{Y}$用K-means生成的$\sqrt{K}$个聚类的质心,并分配给其特征节点。
• 也就是说，先找到与样本patch $\pmb{x}$ 相似度相近的某个聚类，在根据这个聚类找到与这个聚类相似的$\sqrt{K}$个聚类，这$\sqrt{K}$个聚类即为样本patch $\pmb{x}$的近邻集合$\pmb{D}$。

4. 密度图重构

• 采用基于流形假设的非参数方法来学习权重$\pmb{w}$，再用$\pmb{w}$来计算密度图$\pmb{x}_d$
• $$\pmb{w}^* = arg\,\min_{\pmb{w}} \mathcal{J}(\pmb{w|x,D})~~~~~~s.t. \pmb{1^Tw}=1$$ $\mathcal{J}(\pmb{w|x,D})$是损失函数，对$\pmb{w}$做优化
• 那么$\pmb{x}_d$可以计算为：$\pmb{x}_d≌\pmb{D}_d$

四、M-VOC 算法

• 目标是最小化权重$\pmb{w}$

  $$\pmb{w}^* = arg\,\min_{\pmb{w}}||\pmb{x}-\pmb{Dw}||_2^2 ~~~~~~~s.t. \pmb{1^Tw}=1\tag{6}$$

  • 如果$\pmb{D}^T\pmb{D}$是正定的，那么$\pmb{w}$可以求解为：$\pmb{w}^*=\frac{1}{Z}(\pmb{D}^T\pmb{D})^{-1}\pmb{D}^T\pmb{x} \tag{7}$ $Z$ 是归一化因子。
    公式（7）的方法被命名为M-VOC(LS)。

  • 若图像块维度$q_1>T$,那么$\pmb{D}^T\pmb{D}$不是正定的，则上述方法不适用，于是在这里引入正则化项。
    1）energy：为了产生更稳定的局部权重，$\pmb{w}$会受到其energy的限制。
    2）稀疏性：M-VOC受到patch的邻域大小限制，若T太小，则领域不足以表征局部几何形状，相反，则会倾向不同局部几何形状的邻域。这里引入局部约束和稀疏约束来避免T的选择。
    3）非负性：对$\pmb{w}$负约束可以使相似的图像块和图像密度凸组合。
    4）局部性:当选取邻域重构$\pmb{x}$，局部性已经被隐含地假定。

• 基于以上四个约束，$\pmb{w}$的优化公式可以写作：$\pmb{w}^* = arg\,\min_{\pmb{w}}||\pmb{x}-\pmb{Dw}||_2^2+\lambda_1||\pmb{w}||_2^2+\lambda_2||\pmb{w}||_1+\lambda_3(\pmb{w}-0)$ $s.t. \pmb{1^Tw}=1~~and~~\lambda_1,\lambda_2,\lambda_3\ge0 \tag{8}$第二项以低能量强制$\pmb{w}$，而第三项强制稀疏性以选择潜在候选。第四项确保$\pmb{w}$是正的。
• 为了从(8)中获得更多的解，通过设置不同的$\lambda_1,\lambda_2,\lambda_3$，可以获得如下三个变量:
  1）M-VOC(e)
  令$\lambda_2=0,\lambda_3=0$ $$\pmb{w}^* = arg\,\min_{\pmb{w}}||\pmb{x}-\pmb{Dw}||_2^2+\lambda_1||\pmb{w}||_2^2$$ $$s.t. \pmb{1^Tw}=1~~and~~\lambda_1\ge0 \tag{9}$$ $q_1>T$，公式（9）可以优化为：$\pmb{w}^*=\frac{1}{Z}(\pmb{D}^T\pmb{D}+\lambda_1\pmb{I})^{-1}\pmb{D}^T\pmb{x} \tag{10}$
  2）M-VOC(s)
  令$\lambda_1=0,\lambda_3=0$
  $\pmb{w}^* = arg\,\min_{\pmb{w}}||\pmb{x}-\pmb{Dw}||_2^2+\lambda_2||\pmb{w}||_1$ $s.t. \pmb{1^Tw}=1~~and~~\lambda_2\ge0 \tag{11}$可用Lasso方法优化
  3） M-VOC(nn)
  令$\lambda_1=0,\lambda_2=0$
  $\pmb{w}^* = arg\,\min_{\pmb{w}}||\pmb{x}-\pmb{Dw}||_2^2+\lambda_2||\pmb{w}||_1$ $s.t. \pmb{1^Tw}=1~~and~~\lambda_2\ge0 \tag{12}$可用二次规划优化。

五、KM-VOC 算法

• 图像块包含许多变化，如形状和纹理，并且如以上部分所讨论的线性表示可能无法完全捕捉它们潜在的内在关系。本文首先将非线性映射引入到模型的局部几何建模中，然后应用核方法使其易于处理。
• 使用非线性映射，则 $\pmb{w}^*$变为： $$\pmb{w}^* = arg\,\min_{\pmb{w}}||\phi({\pmb{x}})-\pmb{\phi{(D)}w}||_2^2+\lambda||\pmb{w}||_2^2$$ $$s.t. \pmb{1^Tw}=1~~and~~\lambda\ge0 \tag{14}$$ 则闭式解为： $$\pmb{w}^*=\frac{1}{Z}(\phi(\pmb{D})^T\phi(\pmb{D})+\lambda\pmb{I})^{-1}\phi(\pmb{D})^T\phi(\pmb{x}) \tag{15}$$
• 用核函数表示非线性映射，则公式（15）可以表示为 $\pmb{w}^*=\frac{1}{Z}(\pmb{G}+\lambda\pmb{I})^{-1}k(\pmb{D,x}) \tag{16}$ $G$是GRAM矩阵，$G_{i,j}=\phi(\pmb{y}^t_i)^T\phi(\pmb{y}^t_j)$, $k(\pmb{D,x})$是核。
• 那么，$\pmb{x}_d$可以被重构为： $\pmb{x}_d≌\pmb{E}k(\pmb{D,x}) \tag{17}$ 其中$\pmb{E}=\pmb{D_d}(\pmb{G}+\lambda\pmb{I})^{-1}$,为嵌入矩阵