论文题目：Active Shape Model - their training and application
论文作者： $T.F.Cootes, C. J. Taylor, D. H. Cooper, J. Graha$
Implementation: https://www.mathworks.com/matlabcentral/fileexchange/26706-active-shape-model-asm-and-active-appearance-model-aam
论文原文中的一些翻译可能不准确，（）中的部分为论文原文中的术语

摘要

基于模型的视觉(model-based vision)在识别和定位刚性物体方面都是具有鲁棒性(robustness)的方法。将基于模型的方法应用在一些可能会产生外形变化的图片上时，会产生问题。这些灵活的模型为了适应图片中物体外形的变化，会牺牲自身模板本来的形状，因此鲁棒性会降低。本文指出，一个模型只能在其所代表的属类下进行特征变换。文章提出了一种从具有多重差异的训练集中学习模式特性来建立模型的方法。这些模型可以被用来进行迭代的图片搜索，和Active Contour Models(snakes)相似。两种的主要哲别是文章提出的ASM 模型只可以应用于和训练集模型相似的变形。

介绍

本文主要贡献是描述了如何建立一个基于某特殊种类但仍具有相当多可变性的的模型。文章的技术基于由一个点集表示的个体或图片中的某种结构。在训练集中，每个example的点集排布的顺序是一样的，这些来自不同example的点集中的被自动匹配出来最小化对应点的差异。通过检测这些点的数据导出一个 Point Distribution Model. 这个模型会给出平均的每个点的位置，并且有一些参数来控制训练集example中每个点的差异变化。

背景介绍

这部分写少了一些灵活模型或者可变的模板来帮助进行图片判读。

“Hand Craft” Models

Articulated Models

Active Contour Models(Snakes)

Fourier Series Shape Models

Statistical Models of Shape

Finite Element Models

点分布模型（Point distribution Model）

这部分以“建立电路板上的电阻的形状模型”为题进行解释。给出的图则是电路板上一些常见的电阻的形状，虽然这些图形都是电阻（也就是文章提到的对于某个特定的class而言），但是这些电阻的形状也不完全相同（也就是文章提到的具有considerable variability）。这样这些形状的电阻就构成了训练集。文章要利用这个训练集来建立一个描述电阻形状的模型。需要做的是：1. 对于每一个example标记一系列的特征点(landmark) ；2. 计算每一个点的平均位置和平均位置到每个example中该点的路径。

Labeling the training set

为了对电阻的形状建模，我们需要在电阻这个形状的边界（boundary）选择一些点。

每一个被选中的点都代表电阻的一部分或是边界的一部分。为了保证模型的精确，我们必须保证相同序号的点表示的是电阻的同一部分，比如每个一example点集中的【点0 】必须表示的都是该电阻左侧的头，【点31】必须表示的是电阻左侧的尾（即与starting point相连接的地方。）在训练部分，为了保证标记点的正确性，我们需要手动标点。但是模型训练完毕之后，我们就可以用这个模型来预测一切电阻类形状的边界和各个特征点的位置。

我们这里标记的特征点有三种：

标记了物体应用相关（application-dependent）的点：比如在脸部模型中眼睛的中心位置，边界点中急转的位置；
标点了物体应用无关（application-independent）的点：某个特定方向上的最高点，曲率最大处。
其他的可以是由1，2得到的插入点。

用这三类点来描述物体形状的边界就足够了

Aligning the Training Set

为了对不同形状（也就是来自不同example的边界）上的等价点（equivalent points）进行比较，这些点必须进行匹配。我们使用放缩，旋转和平移来尽可能缩小等价点之间的距离。

首先来讨论匹配一对形状上的等价点。用 ${\bf x}i$ 向量表示第 $i$ 个形状上的 $n$ 个点。${\bf x}_i = (x{i0}, y{i0}, x{i1}, y{i1},…,x{in-1}, y{in-1})^T$ , 用 $M(s,\theta)[{\bf x}]$ 表示经历旋转 $\theta$ 和缩放 $s$ 。那么，当给了我们两个相似的形状 ${\bf x}_i $ 和 ${\bf x}_j$ 时，我们选用旋转矩阵 $\theta_j$,缩放系数 $s_j$ 以及平移 ($t{xj}, t_{yj}$) 对 ${\bf x}_j$ 做一系列变化，使得变化后的 ${\bf x}_j$ 和 ${\bf x}_i$ 相差最少。定义的权重和为：

$Ej = ({\bf x}_i - M(s_j,\theta_j)[{\bf x}_j] - {\bf t}_j)^T {\bf W}({\bf x}_i - M(s_j,\theta_j)[{\bf x}_j] - {\bf t}_j)$ , 这里的 ${\bf W}$ 为对角矩阵，对角线上的每个值是对应点的权重。越稳定的点，权重越大。定义第 $k$ 个点的权重的表达式： $w_k = (\sum\limits^{n-1}{l=0}V{R{kl}})^{-1}$. 这里 $ R{kl}$ 表示的是点 $k$ 和点 $l$ 之间的距离。 $V{R_{kl}}$ 表示的是在训练集所有的形状中，点 $k$ 和点 $l$ 之间的距离的方差。这样就说明了，如果一个点相对是固定的，那么这个点和其他点之间的距离变化会比较小，导致方差小，因而权重变大。那么这些点在匹配的过程中所占的地位就优先。

以下是对一个example 的shape中的 $N$ 个点进行匹配的过程：

- Rotate, scale, and translate each shape to aligh with the first shape in the set
- Repeat
		- Calculate mean shape from the aligned shapes
		- Normalize the orientation, scale and origin of the current mean to suitable defaults
		- Realign every shape with current mean
- Until the process converge

检测是否收敛：可以查看在匹配每一个shape时所需要的平移的值是否在减小。

Capturing the Statistics of a Set of Aligned Shapes

当我们在做了一系列操作将每一个exmaple中的shape和mean shape进行匹配后，可以发现在这些shapes叠放在一起时，有一些标记点的差异性比较大，有一些标记点的差异性比较小。这里就引入了 Point Distribution Model（PDM）对这些有差异性的点进行建模，但是，需要注意的是，每一个标记点都不是独立的，他们都是和一部分其他的标记点相关的。

在对这些点进行了匹配之后，每一个example都可以用一个 $2n$ 维的向量来表示（之前提到的向量 ${\bf x}_i$ 的维度）。这样训练集中的 $N$ 个example就在 $2n$ 维的空间中给了我们 $N$ 个点。如果假设这些点都在 $2n$ 空间的某个区域，我们将这个区域成为 Allowable Shape Domain. 那么每一个在这个区域的 $2n$ 维的点都会有相似的形状。一下将会介绍在更高维度来抓住每一个标记点之间的关系。首先需要 1. 假设这个点云是椭圆体的； 2. 计算这 $N$ 个点的中心（也就是平均形状）；3. 计算它的主坐标轴（axes）。

如果已有 $N$ 个已匹配的形状，那他们的平均形状（mean shape） $\bar{\bf x} = \frac{1}{N}\sum\limits^{N}_{i = 1}{\bf x}_i$，就是 $2n$ 维空间中椭圆体的中心。$2n$ 维的椭球体可以利用 PCA来计算他们的主轴，每一个轴都代表一种差异（variation），这些差异就是训练集中不同的形状在 $2n$ 维空间的表示。

对于每一个在训练集中的形状：

计算它和平均形状 $\bar{\bf x}$ 的差值（deviation）： $d{\bf x}_i = {\bf x}_i - \bar {\bf x}$
计算这个 $N$ 个点的 $2n\times 2n$ 维的协方差矩阵（covariance matrix）${\bf S}$ : ${\bf S} = \frac{1}{N}\sum\limits^{N}_{i = 1}d{\bf x}_id{\bf x}_i^T$
计算矩阵 $S$ 的本征值 $\lambda$ (eigenvalue)和本征向量 ${\bf p}$（eigenvector）: ${\bf Sp}_k = {\bf \lambda}_k{\bf S}$，且 ${\bf p}_k^T{\bf p} = 1$

(一般在做PCA的计算时，本征值按从大到小的顺序排列，因此 ${\bf\lambda}k >= {\bf\lambda}{k+1}$, 本征值越大表示其对应的本征向量的方向上，数据的差异性越大。PCA 就是帮助我们找出在$2n$ 维空间中，数据差异最大的方向向量)
为了缩小本征向量的数量，我们可以只取 $t$ 个本征向量来估计这个处在 $2n$ 维的数据。一般这个 $t$ 值取决于前 $t$ 个本证值的和占总本征值和的比例。
每一个训练集中的数据都可以用平均形状 $\bar {\bf x}$ 和特征向量的线性组合表示。如果我们只取特征向量的前 $t$ 个，那么训练集中的每一个example都可以用 ${\bf x} = \bar{\bf x} + {\bf Pb}$ 表示，这里的 ${\bf P }= ({\bf p}_1, {\bf p}_2, …{\bf p}_t)$ 表示特征向量, ${\bf b} = (b_1, b_2, …b_t)^T$表示权重。

（以上的公式同样可以帮助我们生成新的不在训练集中，但是却和训练集中数据相似的example）

（基于常见的模型， $ b_k$ 和 ${\bf \lambda}_k$ 的关系如下： $-3\sqrt{\lambda_k}\leq b_k \leq 3\sqrt{\lambda_k}$ ）

Practicle example

这部分给出了一些作者应用的实例，分别是电阻的模型，心脏的模型，手的模型以及幼虫模型。

在图片搜索中应用点分布模型（Using point distribution models in image search.）

之前的第三部分主要说的是给出的训练集是点集的时候，如何对这些点集建模，构建点分布模型。这部分要说的是如何把点分布模型应用在图片中搜索目标形状，也就是 Active Shape Model. 这部分包括了找到图片中的形状，并且把模型放置在目标形状上。

这部分模型的定义：

${\bf X} = M(s, \theta)[{\bf x}] + {\bf X}_c$,

${\bf X}_c = (X_c, Y_c, X_c, Y_c,…,X_c, Y_c)^T$, $M(s, \theta)[{ \cdot}]$ 和之前一样表示的是旋转和缩放的操作， $(X_c, Y_c)$ 表示的是在图片坐标下(iamge frame)模型的中心。

这部分我们介绍了一个给定初始位置，找到合适的 $\bf X$ 的位置的迭代方法。主要就是从初始位置开始检测图片的区域，然后调整 $\bf X$ 上点的位置。$\bf X$ 上局部点的位置会影响到整体 $\bf X$ 的姿态，缩放，以及形状参数，这个步骤一直不断重复直到 $\bf X$ 上的点没有大的变化。

Calculating a Suggested Movement for Each Model Points.

当给定了 $\bf X$ 的初始设定和图片物体时，我们需要针对图片对$\bf X$ 进行调整。我们需要将 $\bf X$ 上的点移动到更加靠近图片边界的位置。文章中使用的方法是在模型边界的方向量上向图片的边界移动。或者可以生成替代的图片，描述每个点可能成为新的 $\bf X$ 上一点的可能性。无论使用哪种方法，我们都可以得到model上每一点的调整向量， $d{\bf X} = (dX0, dY_0, …dX{n-1}, dY_{n-1})^T$

Computing Changes in the Pose and Shape

上面一部分说明了针对 $\bf X$ 上每个局部的点是如何调整位置的，这部分需要说明的是局部调整的位置对全局的模型姿态和形状参数的影响。

我们的目标是调整整体模型的姿态和形状参数，使得现在的模型$\bf X$ 可以移动到新的位置 ${\bf X} +d{\bf X}$ ，并且可以保持本来的形状。如果现在模型的中心是 $(X_c, Y_c)$, 方向是$\theta$ ，缩放程度是$s$，我们首要考虑的是如何更新这些参数让更新后的模型更加贴合图片本身。通过利用附录A中的方法，寻找位移变量$(dX_c, dY_c)$, 旋转变量 $d\theta$, 缩放变量 $(1+ds)$ 使得现有的的模型 ${\bf X}$ 在变化过后更加靠近 $({\bf X} + d{\bf X})$。

我们希望在局部坐标系(local frame)下计算调整量 $d{\bf x}$ 使得模型 ${\bf X}$ 在经过之前计算的变化量（唯一变化量，旋转变化量，缩放变化量）之后和 $d{\bf X}$ 变化后更加贴近。这里说的大概意思就是使得$M(s(1+ds), \theta+d\theta)[{\bf x}+d{\bf x}] + {\bf X}_c +d{\bf X_c}$ 之后的模型更加贴近 $({\bf X} + d{\bf X})$，不光模型在图像坐标系下的平移旋转和缩放有改变，他本身的姿态和形状也有有所改变。

因此

$M(s(1+ds), \theta+d\theta)[{\bf x}+d{\bf x}] + {\bf X}_c +d{\bf X_c} = ({\bf X} + d{\bf X})$

$M(s(1+ds), \theta+d\theta)[{\bf x}+d{\bf x}] = ({\bf X} + d{\bf X}) - ({\bf X}_c +d{\bf X_c})$

又因为：${\bf X} = M(s, \theta)[{\bf x}] + {\bf X}_c$

因此：$M(s(1+ds), \theta+d\theta)[{\bf x}+d{\bf x}] = (M(s, \theta)[{\bf x}] + {\bf X}_c + d{\bf X}) - ({\bf X}_c +d{\bf X_c})$

因此：$M(s(1+ds), \theta+d\theta)[{\bf x}+d{\bf x}] = (M(s, \theta)[{\bf x}] + d{\bf X}) - d{\bf X_c}$

因为：$M^{-1}(s, \theta)[\quad] = M(s^{-1}, -\theta)[\quad]$

所以：$d{\bf x} = M((s(1+ds))^{-1}, -(\theta +d\theta))[{\bf y}] - {\bf x}$, where ${\bf y} = M(s, \theta)[{\bf x}] + d{\bf X} - d{\bf X_c}$

这里 $d{\bf x}$ 的变化是在local frame里的变化，为了让 $d{\bf x}$ 的变化符合形状的constraint，我们需要将 $d{\bf x}$ 转换到parameter space, 然后计算parameter $\bf b$ 的变化量 $d{\bf b}$ ，使得其产生的变化在二维平面更加接近$d{\bf x}$ 。

在之前的部分分析在PCA space也就是 parameter space分析模型的时候指出： ${\bf x} = {\bar {\bf x}} + {\bf Pb}$，因此在此处我们需要找到的parameter的变化量为${\bf x} +d{\bf x} \approx \bar{\bf x} + {\bf P}({\bf b} + d {\bf b})$, 因为在parameter space 我们只取了 $t$ 个向量，所以这里只能是估计。

因此 $d{\bf x} = {\bf P}(d{\bf b})$, so $d{\bf b} = {\bf P}^{-1}d{\bf x}$, 因为 ${\bf P}$ 中的向量是相互垂直且长度为 1，所以${\bf P}^{-1}={\bf P}^T$

Updating the Pose and Shape Parameters

这部分介绍了在之前提过的计算调整量，使得调整过后的模型更加接近图像中的object之后，我们该用怎样的顺序更新姿态（pose）和形态（shape）的变化量：

姿态的变量主要是基于图片坐标系下的平移旋转和缩放变量：$dX_c, dY_c, d\theta, ds$
形态的变量主要是基于PDM模型本身的形状变化，应用的是在training example中学到的variability：$d{\bf b}$

这里对参数进行的更新是循环更新：

$X_c\longrightarrow X_c +w_tdX_c$

$Y_c\longrightarrow Y_c +w_tdY_c$

$\theta \longrightarrow \theta + w_\theta d\theta$

$s \longrightarrow s + w_sds$

${\bf b} \longrightarrow {\bf b} + {\bf W_b} d{\bf b}$

这里的 $wt, w\theta, w_s$ 都是标量权重，${\bf W}_b$ 是包含权重的对角矩阵。

当Mahalanobis 距离 $Dm$ 小于一个定量 $D{max}$时，此时拟合出来的形状是可以接受的

Practicle Example

同样是对之前做过点模型的例子再进行图片搜索找到模型点的例子。

个人总结

这篇文章主要探讨的就是一个点模型和如何在图片中应用点模型进行搜索和特征点定位。这里训练集的点模型必须是一系列相似形状的，且有序标注了特征点的模型。训练好的模型可以被运用在一张新的图片中寻找合适的属于这个图片上的等价特征点。

不太懂的点：

主要还不太清楚的模型是点模型在被放在图片上之后，如何进行调整量 $d {\bf X}$的搜索（如何得到suggested point）。这点在Statistical models of appearance for computer vision 中page 34有所介绍，也是另一篇博客介绍的对于点模型上每一个点建立局部特征的依据。
文中提到说，如果没有初始的位置设定，可以利用遗传算法来确定object的位置。后面有提到遗传算法的文章，看看有没有时间补一下。