最小路径模型

机器学习

---

常见使用场景

最小路径模型（MISCP）在描述同一物体的形状变化时，采用的方法和ASM模型一样，也是通过建立PDM来构建形状向量。但是ASM 在搜索目标图像的各个标记点的最佳位置时，是不断在形状和灰度信息中切换的。最小路径模型对此进行了优化，使形状和灰度模型在一个使用动态规划而非迭代的代价函数中结合起来使用。此外，在目标图像的搜索阶段，MISCP 会在目标图像中搜索一组与训练样本中标记点的灰度信息相似的候选点，而并非像ASM模型直接选择一个候选点作为局部最优解。这样可以很好避免由于噪声使灰度模型搜索到错误的点，最终导致整个形状将被引导到一个错误的位置。该算法相对于ASM，有很好的识别率，正因为该算法的高效性，它经常被用于许多医疗图片切割。

MISCP算法

MISCP 并非直接在原始图像上进行搜索和训练，而是在一组特征图像上进行搜索和训练，因此，我们首先对训练集中每个样本构建六副特征图，然后和ASM一样，使训练集中的样本对齐，配准并计算平均形状模型，同时根据训练样本建立灰度模型和形状模型。然后在搜索目标样本图像时，计算出一个初始位置，随后通过灰度模型在目标图像上搜索一组与训练集中标记点的灰度信息相似的候选点，当得到一定数量的候选点后，再结合形状模型使用动态规划的代价函数，最终得到最优的形状向量。具体流程如下图所示。

特征图的建立

建立特征图像可以有效避免噪声对候选点选取的影响，因此，对于每个训练集的样本和目标图像，我们都会为其建立六种特征图像，并且在之后对灰度信息的分析和统计均是在这六幅特征图像上进行，而非原始图像。这六副特征图像分别是原始图像每个像素点灰度值在X轴上的一阶偏导，X轴上二阶偏导以及混合偏导，在Y轴上的一阶偏导，Y 轴上二阶偏导，在X 轴上二阶偏导和在Y 轴上二阶偏导之差

灰度模型的建立

对于每一个标记点我们将统计它的灰度信息，这样在图像搜索阶段时，我们可以根据训练集中标记点的灰度信息得到一组与之相似的候选点。

我们定义一个标记点的灰度代价函数$h_i(p,I)$，它可以算出在图像$I$中的点$p$和训练集中第$i$个标记点之间的灰度信息的相似度。$h_i(p,I)$的值我们称为灰度代价，因此，图像中灰度代价最低的点将构成一个最有可能和真实轮廓相吻合的最佳轮廓。具体步骤如下：

为了采集点$p$ 附近的区域的灰度信息，我们首先将对于每一幅训练集的样本图像$I$计算六个特征图像$I^{[1,2,..,6]}$，分别为 X 一阶偏导图像，X二阶偏导图像，XY混合偏导图像，Y一阶偏导图像，Y二阶偏导图像和X，Y二阶偏导和的图像，然后我们将采集分别在六副特征图像以点$p$为圆心$r_c$为半径的圆上所有点的灰度信息并且对其标准化，设$g_i^{[j]}$表示第$i$个标记点在第$j$个特征图的圆形灰度向量，接着我们将对整个训练集的所有样本求每个标记点在每个特征图上的平均灰度信息$\overline g_i^{[j]}$和协方差矩阵$S_i^{[j]}$。
点$p$ 的灰度代价$h_i(p,I)$的算法如下：首先获取点$p$ 在六副特征图的灰度向量$g^{[1]},g^{[2]},...,g^{[6]}$ ，然后计算每个灰度向量$g_i^{[j]}$ 和第$i$ 个标记点的平均灰度向量$\overline g^{[1]} ,\overline g^{[2]} ,...,\overline g^{[6]}$的马氏距离，最后用下列计算式求的点$p$的灰度代价。

$$h_i(p,I)=\sum_{j=1}^6\left(g^{[j]}-\overline g^{[j]}\right)^TS_i^{[j]}\left(g^{[j]}-\overline g^{[j]}\right)$$

形状模型的建立

类似于ASM 方法，形状模型的建立是为了约束目标图像的形状，使分割的目标形状相似于训练集。然而与ASM 不同的是，MISCP 并不是将所有的点集中在一个形状向量中去计算相关性，而仅仅计算相邻两个标记点的形状向量$v_i$ ，设两点分别为$p_i=(x_i,y_i),p_{i+1}=(x_{i+1},y_{i+1})$ ，则$v_i=(x_{i+1}-x_i,y_{i+1}-y_i)$和灰度模型类似，我们也将构造形状代价函数$f_i$ 去计算当搜索目标图像的轮廓时，目标图像的形状向量$v_i$ 和训练集的统计形状向量$\overline v_i$ 的相似性。
相邻两点的形状向量$v_i$ 的形状代价$f_i(v_i)$的算法如下：首先我们将计算每两个相邻标记点在训练集的平均形状向量$v_i$ 和协方差矩阵$S_i$，然后计算形状向量$v_i$ 和平均形状向量$\overline v_i$的马氏距离，即形状向量$v_i$ 的形状代价。

$$f_i(v_i)=(v_i-\overline v_i)^TS_i^{-1}(v_i-\overline v_i)$$

MISCP 的搜索算法

在搜索目标图像的最佳形状时，我们会使用之前建立的灰度模型与形状模型，但与ASM 不同的是，MISCP 算法并不是通过迭代去搜索最佳形状，而是通过以下两步去找到最佳形状。

第一步：搜索候选点：对每个标记点$p_i$通过灰度模型在六副特征图中的一个特定区域里找到前$m$个灰度代价最小的候选点。但是，对于每一个标记点的搜索区域大小是不一样的，如果标记点的搜索区域过大，搜索区域会将肋骨等边界区域包含进去，导致产生大量干扰点。相反，如果标记点的搜索区域过小，可能不能覆盖真实的肺边界，使搜索陷入局部极值。同时，由于肺的上部和下部形状变化较大，相对位置各不相同，所以需较大的搜索区域，肺中间区域的点相对初始位置变动较小，故用相对较小的搜索区域即可。如下图所示，图中红色方框就是第11 个训练样本中第5 个标记点的搜索区域。

设点$p_{i1},p_{i2},...,p_{im}$是第i 个标记点$p_i$ 的灰度代价最小的候选点。当每个标记点$p_i$ 都找到了 $m$ 个候选点，我们将构建一个$n\times m$的灰度代价矩阵$C$。其中矩阵中第i 行就是第i 个标记点的m 个候选点。

$$C=\begin{bmatrix} p_{11}& p_{12}& ...& p_{1m}\\ p_{21}& p_{22}& ...& p_{2m}\\ ...& ...& ...& ...\\ p_{n1}& p_{n2}& ...&p_{nm} \end{bmatrix}$$

第二步：选择最小代价路径：我们要找到一个矩阵$C$中的最优候选点组合并作为目标图像的最佳轮廓。首先，在矩阵$C$ 中每行选取一个候选点，即每个标记点选取一个候选点作为该标记点的最佳位置，当我们为每个标记点都选取了一个候选点后，则这些被选取的候选点就构成了目标图像的一个轮廓。如果这些候选点构成的形状轮廓是灰度代价和形状代价最小的，那么我们就找到最佳轮廓。假设第i 行选中点的下标为i k ，则形状轮廓为$(p_{1k_1},p_{2k_2},...,p_{nk_n})$ 。现在，当我们在搜索最优路径时，我们需要考虑两种代价：

1. 灰度代价$h_i$ ：每个点的灰度代价已经赋值到矩阵中各个节点（第i 个点的m 个灰度代价就是矩阵$C$ 的第i 行的m 个节点中的值）。
2. 形状代价$f_i$ ：第i 个点的形状代价是通过节点i 和节点i+1 计算而得。先从第 i+1行$i=(1,2,...,n-1)$选取一个候选点 $p_{i+1}$ ，然后计算该候选点$p_{i+1}$ 和第i 行每一个候选点$p_i$ 的形状代价和候选点$p_i$的灰度代价之和，选取它们中总代价最小的第i 行候选点$p_{ik_i}$ ，然后将$p_{ik_i}$的总代价和$p_{i+1}$ 的灰度代价加起来作为候选点$p_{i+1}$ 的总代价，并将$p_{ik_i}$ 和$p_{i+1}$ 记入候选路径，依此类推，直到计算到最后一行。然后我们从最后一行的m 个候选点中选取一个总代价最小的候选点，此时以总代价最小的候选点作为候选路径的组合就是一条总代价最小的轮廓，该轮廓就是MISCP 搜索的形状。如下图所示，图中黄色的点就是每个标记点的候选点，本文中每个标记点有30 个候选点，图中白色线代表初始位置，图中红色的线就是MISCP 搜索的最佳轮廓。
   

MISCP 模型类似于ASM 模型，形状都被表示为一组标记点的形状向量，与ASM的做法不同，该模型并不是把所有标记点构成的形状向量当作形状特征，而是通过建模每两个相邻标记点的相对位置来获得局部形状特征。此外，MISCP 在训练和搜索阶段，使用的都是特征图像，这样可以降低噪声的干扰。在分割过程中，每个标记点的候选点的检测是通过扫描特定区域来获取前m个灰度代价最小的候选点，所有标记点的m个候选点将构成一个灰度矩阵。然后选择一个最优候选点组合作为目标图像的最佳轮廓，其中，每个候选点的选择使用动态规划的方法，同时考虑了候选点的灰度和形状信息。

参考资料

1. http://en.wikipedia.org/wiki/Procrustes_analysis