A Semi-supervised Affinity Propagation Clustering Method with Homogeneity Constraint
-
摘要: 以近邻反射传播 (Affinity propagation, AP) 聚类算法为基础, 提出了一种基于同类约束的半监督近邻反射传播聚类方法 (Semi-supervised affinity propagation clustering method with homogeneity constraints, HCSAP).该方法在聚类目标函数中引入同类约束项, 以保证聚类结果与同类集先验信息一致.利用最大和信任传播 (Max-sum belief propagation) 优化过程对目标函数进行求解, 导出同类约束下的吸引度 (Responsibility) 和归属度 (Availability) 的迭代方程.人工数据集和真实数据集上的实验结果表明本文所提方法的有效性.Abstract: In this paper, a semi-supervised affinity propagation (AP) clustering algorithm with homogeneity constraint, called HCSAP (semi-supervised affinity propagation clustering method with homogeneity constraints), is proposed. To keep consistency between the clustering results and the priori information about homogeneity sets, the constraint terms are introduced to the objection function of algorithm AP. With the max-sum belief propagation procedure, the objection function can be resolved into the corresponding responsibility and availability update equations. Experiments on synthetic dataset and real-world datasets indicate the effectiveness of the proposed HCSAP.
-
脊柱类疾病是比较常见的一种疾病, 手术是治疗脊柱类疾病的常见方式.图像引导的脊柱手术能够大大提高手术的成功率, 尤其是3D的图像能够给医生提供包括病人脊椎姿态的丰富信息.然而在术中获取病人的3D影像是十分困难的, 而获得2D的X-ray图像比较容易, 为了在术中给医生呈现病人的3D脊椎信息, 一个可行的方法便是对术前3D图像中的脊椎和术中2D图像中的脊椎进行配准, 从而间接地在术中为医生提供病人脊椎的3D姿态信息.
如图 1所示, 传统的2D/3D配准方法是基于搜索的策略, 是将3D图像模拟投影成一系列的2D图像, 将这些模拟投影图像与真实的2D图像进行相似性度量, 找到一个最佳匹配的模拟投影图像, 从而完成配准[1-4].在进行相似性度量时, 早期配准方法如[2, 4-7]是对整幅图像或感兴趣区域进行配准, 这样目标周围的组织也会对配准产生影响.为了避免邻近组织的影响, Pohl等在配准前先对目标进行分割, 使得配准更加的精确[8].在搜索的策略上, 由于投影空间复杂度较高为O(n6), 包括3个平移自由度和3个旋转自由度, 所以计算量巨大, 为了减小计算量, 有许多启发式搜索的方法被提出, 如Zollei等和Kim等使用梯度下降的方法来引导搜索[5-6], Chou等使用回归学习的方法建立灰度残差与投影参数改变量的关系来引导投影参数的搜索方向[9].这些基于启发式搜索的配准方法在一定程度上减小了计算量, 但是依然很难达到实时配准, 并且对初值敏感, 不易收敛.
由于基于搜索策略的配准方法计算量大, 越来越多的研究转向基于机器学习的方法[10-12].基于机器学习的配准方法主要是学习模拟投影图像与投影参数之间的关系, 从而避免搜索的过程, 大大提高了配准的效率.使用投影图像的哪些信息以及如何提取这些信息并建立与投影参数之间的关系是基于机器学习配准方法的一个重要的问题. Cyr等只使用了简单的轮廓信息, 而没有使用内部丰富的结构信息[10].文献[11]中建立了目标的纹理模型, 并学习纹理模型与投影参数之间的关系, 在精度和速度上都有较好的效果, 但是这个工作配准的对象是干扰较小的头部图像, 因此并没有分割的过程.文献[12]中使用标志点的统计分量来回归学习其与投影参数之间的关系, 但是其将分割、标志点定位和统计分量计算作为三个独立的问题进行处理, 且分割直接使用人工设定阈值的方法, 使得整个方法复杂且需要较多的人为干预, 稳定性和实用性欠佳.
为了更好地分割目标, 本文对脊椎建立了统计形状模型[13-14].统计形状模型最早应用于人脸分割上, 文献[15-16]将统计形状模型应用在医学影像的分割上, 得到了不错的效果.统计形状模型除了分割目标外, 还能提取形状分量、灰度分量、标志点位置等信息, 相比文献[12]中将这三个步骤作为三个独立的问题进行处理, 统计形状模型具有更高的稳定性和实用性.文献[11]中使用了灰度信息建立了纹理模型, 但是2D/3D配准是跨模态的, 灰度信息易受到模态的影响, 而形状信息并不会受到模态的影响, 因此本文采用形状信息建立与投影角度的关系, 即姿态模型.
另一方面, 可以证明6个投影参数, 在选择合理的投影方式下, 其中4个投影参数的效果可以等效为一个仿射变换, 有了标志点的位置, 可以通过几何的方法直接计算出这个仿射变换, 因此姿态模型只需要建立两个投影参数与形状分量的关系.
基于以上考虑, 本文提出了一个结合几何与学习的2D/3D脊椎配准方法, 该方法使用统计形状模型对目标脊椎进行分割并提取形状信息, 在一个本文构建的新的投影方式下, 两个参数通过学习求解, 其余4个投影参数通过几何求解.
本文的主要贡献如下:通过学习的方法建立投影图像与投影参数之间的关系, 构建了一个新的投影变换方式, 使用几何和学习相结合的方法计算投影参数.故而, 本文的方法实时性好, 准确性高, 鲁棒性好.
1. 方法
1.1 总体流程
如图 2所示, 本方法主要包括三个部分.第一部分为建立统计形状模型, 在术前使用训练集的CT图像投影生成2D的DRR (Digitally reconstructed radiograph)图像, 并和X-ray图像一起建立统计形状模型AAM (Active appearance model); 第二部分为建立姿态模型, 在术前对病人的CT图像进行DRR投影, 使用AAM模型分割DRR图像中目标脊椎, 并得到形状参数, 然后建立投影参数与形状参数之间的关系; 第三部分为配准, 在术中, 使用AAM模型对X-ray图像的目标脊椎进行分割, 并得到形状参数, 再使用姿态模型通过形状参数直接得到投影参数, 从而完成配准.
1.2 建立统计形状模型
统计形状模型广泛地应用在医学影像分割当中, 常用的统计形状模型包括ASM (Active shape model)[13]和AAM[14], 其中ASM只对形状信息进行建模, 而AAM不仅对形状信息进行建模同时也对灰度信息进行建模, 因此具有更好的分割性能, 因此本文采用AAM来建立统计形状模型.
本文将3D的CT图像投影成2D的DRR图像, 并对2D的DRR图像和X-ray图像进行AAM建模.为了可以使用同一个统计形状模型来对DRR图像和X-ray进行标志点的定位, 本文将DRR图像和X-ray图像放在一起建立一个统一的AAM模型.
为了提取建立AAM模型所需的标志点, 如图 3所示, 本文对每个样本使用人工提取的方法提取所需的标志点, 并使用普氏分析(Procrustes analysis)[17]将提取的标志点映射到一个共同的坐标系下, 使得每个样本标志点的重心为原点, 并消除平移、放缩、旋转对不同样本标志点的影响.
图 3 提取标志点(我们对每幅图像手动提取93个标志点, 所有标志点总体分为6个部分: (a)为所有的标志点, (b)、(c)、(d)、(e)、(f)、(g)为6个部分每个部分的标志点, 其中(b)为椎体轮廓, (c)为中央灰度凹陷, (d)和(e)接近于生理结构的椎弓根, (f)和(g)为椎体左右下切角)Fig. 3 Extract landmarks (We manually extract 93 landmarks for each image, all landmarks are divided into 6 parts, in which (a) contains all landmarks, while (b), (c), (d), (e), (f), (g) contain one of 6 parts, among them, (b) is vertebral body contour, (c) is the central gray depression, (d) and (e) are close to the pedicle of the physiological structure, and (f) and (g) are the left and right bottom of the vertebral body.)1.2.1 形状模型
本文对映射到共同坐标系下的标志点使用PCA (Principal component analysis)得到形状模型(见文献[13]), 每个样本的特征点$x({x_1},{x_2}, \cdots ,{x_n})$可以表示为
$ x = \overline x + {P_s}{b_s} $
(1) 这里是$\overline x $平均形状, $P_s$是对标志点使用PCA得到的一组标准正交基, $b_s$是形状模型参数.
1.2.2 表观模型
我们把对所有的样本进行变形, 使得其特征点变形到平均形状上(使用三角算法)[18].我们把经过形状标准化的图像, 在其形状模型所覆盖的区域进行采样, 并对采样点进行归一化使其均值为0, 方差为1, 以消除亮度的影响, 从而得到$g$.对$g$我们使用PCA得到表观模型[14], 则$g$可以表示为
$ g = \bar g + {P_g}{b_g} $
(2) 这里$\bar{g}$是平均灰度, $P_g$是灰度模型的标准正交基, $b_g$是灰度模型参数.
1.2.3 联合模型
我们将形状模型参数和灰度模型参数串联起来建立一个联合模型.由于形状模型和灰度模型具有不同的量纲, 因此我们对形状模型加一个系数以统一量纲.
$ b = \left[ {\begin{array}{*{20}{c}} {{W_s}{b_s}}\\ {{b_g}} \end{array}} \right] = \left[ {\begin{array}{*{20}{c}} {{W_s}P_s^{\rm{T}}(x - \bar x)}\\ {P_g^{\rm{T}}(g - \bar g)} \end{array}} \right] $
(3) 其中, $W_s$是一个对角阵来平衡形状模型和灰度模型参数的量纲(见文献[14]).
为了进一步挖掘形状模型和灰度模型之间相关性, 我们对串联的形状模型和灰度模型参数使用PCA得到联合模型(见文献[14]), 由于形状模型参数和灰度模型参数的均值为0, 所以$b$均值为0, 则有:
$ \hat{b}=Qc $
(4) $Q$是表征模型正交基, $c$是表征模型参数:这样我们可以更直接地使用$c$来表达形状和灰度
$ \hat{x}=\bar{x}+P_s W_s Q_s c, \quad\hat{g}=\bar{g}+P_g Q_g c $
(5) 其中
$ Q= \begin{bmatrix} Q_s\\ Q_g \end{bmatrix} $
(6) 1.2.4 分割模型
建立了形状和灰度的联合统计模型之后, 使用该统计模型对目标进行分割, 分割使用迭代的策略.为了使得分割迭代修正的过程更加高效, 分割模型使用了学习的方法, 使用一个线性模型去学习灰度的偏差与联合统计模型参数的偏移量之间的关系:
$ \delta c=A\delta I $
(7) 为了得到A, 在模型的参数上人为增加一个偏移量$\delta{c}$, 计算增加了偏移量之后图像灰度的变化$\delta I$, 使用多元线性回归来拟合$A$.为了拟合平移$t_x$、$t_y$、旋转$\theta$和尺度$s$的变化带来的变化, 在模型参数上增加额外的4个参数($s_x, s_y, t_x, t_y$), 其中$s_x=s \cos (\theta)$, $s_y=s \sin (\theta)$.同时将原图像的灰度$I$标准化后进行采样得到纹理$g$, 则偏移关系变为
$ \delta c=A\delta g $
(8) 其中
$ \delta g=g_s -g_m $
(9) $g_s$为原图像纹理, ${g}_m$为模型的当前迭代联合统计模型的纹理.
1.3 建立姿态模型
由于病人的CT图像可以在术前得到, 所以可以在术前从病人的CT图像中尽可能地获取信息以辅助术中的配准, 提高术中的配准速度和精度.
本节通过对病人术前CT图像投影生成一系列DRR图像, 并使用AAM模型对目标脊椎进行分割得到其统计模型参数, 从这个参数中得到目标脊椎的形状分量和灰度分量.
为了避免配准搜索的过程, 本节建立了姿态模型, 即脊椎和投影参数之间的关系.由于DRR图像和X-ray图像属于不同的模态, 其灰度信息有一定的差异, 因此用DRR图像的灰度信息建立的姿态模型直接应用于X-ray图像并不合适.考虑到脊椎的形状信息不但受模态的影响小而且与投影参数也有较强的相关性, 所以本文使用形状信息来建立姿态模型.
在投影生成DRR图像时, 如果让CT以一些特定的方式变换, 4个投影参数的作用可以等效为一个仿射变换.这就意味着部分投影参数可被几何变换代替.本文构建了一种新的投影变换, 如图 4所示, ($r, \theta, \phi$)为球形坐标系的参数. ($u, v, w$)为投影对象自身姿态坐标系, 此姿态坐标系与球形坐标系联动, 姿态坐标系的$u$轴平行于球坐标系的纬线切线指向如图 4(b)中所示方向, $v$轴平行于球坐标系的经线指向如图 4(b)中所示方向, $w$轴沿径向方法指向背离圆心的方向.
图 4 投影变换((a)图是传统的投影方式, ($x, y, z$)为世界坐标系, ($t_x, t_y, t_z$)是三个平移参数($r_x, r_y, r_z$)为三个旋转参数. (b)图是本文构建的投影方式, ($x, y, z$)为世界坐标系, ($x'O'y'$)为投影平面坐标系, 此坐标系沿世界坐标系$z$轴向投影与($xOy$)重合. ($r, \theta, \phi$)为球形坐标系的参数. ($u, v, w$)为投影对象自身姿态坐标系, 此姿态坐标系与球形坐标系联动, 姿态坐标系的$u$轴平行于球坐标系的纬线切线指向如图 4(b)中所示方向, $v$轴平行于球坐标系的经线指向如图 4(b)中所示所示方向, $w$轴沿径向方法指向背离圆心的方向.)Fig. 4 Projection transformation ((a) is traditional projection transformation, and ($x, y, z$)is world coordinate system, and ($t_x, t_y, t_z$) are three translation parameters, while ($r_x, r_y, r_z$) are three rotation parameters. b) is the proposed projection method. ($x, y, z$) is the world coordinate system, and $x'O'y'$) is the coordinate system of projective plane. This coordinate system coincides with the axial projection of $z$ in the world coordinate system ($xOy$). ($r, \theta, \phi$) are parameters for the spherical coordinate system. ($u, v, w$) is pose projection coordinates of object, and it coact with spherical coordinates as the (b) shows.)为了使问题更加简化且清晰, 本文在对CT投影之前, 先将目标脊椎的中心移动到初始投影位置.对于新的投影方式, 投影过程可以表示为
$ I={ P}({T}(I_{3{\rm D}};r_u, r_v, r_w, r, \theta, \phi )) $
(10) 其中, $I_{3{\rm D}}$为3D图像, $T$为本文构建的三维空间变换, $P$为DRR投影, $I$为投影生成的2D的DRR图像.
由于我们获得X-ray图像生成时, 投影对象距离光源的大致距离$r_0$, 因此可以将$r_0$作为投影的基准值, 实际投影的距离可以表示为$r_0+\delta r$, 这样投影过程可以表示为
$ I={P}({T}(I_{3{\rm D}};r_u, r_v, r_w, r_0 +\delta r, \theta, \phi)) $
(11) 由于$\delta r\ll r_0$, 因此我们可以近似认为$\delta r$的改变所引起的投影图像的变化为一个放缩变换(证明详见附录A).
令
$ I_a={P}({T}(I_{\rm CT};r_u, r_v, 0, r_0, 0, 0)) $
(12) $ I_c={P}({T}(I_{\rm CT};r_u, r_v, r_w, r_0 +\delta r, \theta, \phi )) $
(13) $x^a$为$I^a$某点的坐标, $x^c$为$I^c$中$x^a$的对应点的坐标, 我们把二维的投影坐标系下的坐标点增广表示在三维的世界坐标系中则有$x^A={bmatrix} x^a\\ {h} {bmatrix}$, $x^C={bmatrix} x^c\\ {h} {bmatrix}$. $h$是光源到投影平面原点的距离.则有(证明过程详见附录A)
$ x^C=kRSx^A $
(14) 其中, $k$为一个系数使得等式右边的第三维为$h$, 且
$ S= \begin{bmatrix} s & 0 & 0\\ 0 & s & 0\\ 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} \cos r_w & \sin r_w & 0\\ - \sin r_w & \cos r_w & 0\\ 0 & 0 & 1 \end{bmatrix} $
(15) $ s=\frac{r_0}{(r_0+\Delta r)} $
(16) 其中
$ R= \begin{bmatrix} \cos \theta & 0 & \sin \theta\\ - \sin \theta & \sin \phi & \cos \theta \cos \phi\\ \sin \theta \sin \phi & \cos \phi & - \cos \theta \sin \phi \end{bmatrix} $
(17) $r_u$和$r_v$是空间的旋转参数, 表示的是脊椎的空间姿态, 我们称之为姿态参数, $r_w, \delta r, \theta, \phi$可以使用一个几何变换代替, 我们称之为几何参数.具有相同姿态参数的DRR图像之间可以使用几何变换(齐次空间下)相互转换, 这就意味着对相同的姿态参数只需要投影生成一张DRR图像, 其他相同姿态参数的DRR图像可以通过几何变换的方法得到.这样需要进行DRR投影的参数空间就可以从O($n^6$)减少为O($n^2$).对于图像上的标志点, 同样可以使用线性变换得到, 需要定位标志点位置的图像空间也可以从O($n^6$)减少为O($n^2$), 这样显著的减少了定位标志点的工作量.
为了学习姿态参数与目标脊椎形状参数之间的关系, 对CT图像生成$n$幅DRR图像.对于$n$幅生成的投影图像, 使用AAM分割目标脊椎并获得$n$组形状参数${\pmb B}=(b_1, b_2, \cdots, b_n)$, 每个投影图像对应的姿态参数为
$ \begin{bmatrix} \pmb {R_u} \\ \pmb {R_v} \end{bmatrix} = \begin{bmatrix} r_{u1} & r_{u2} & \cdots & r_{un} \\ r_{v1} & r_{v2} & \cdots & r_{vn} \end{bmatrix} $
本文使用一个线性模型$M$去学习形状参数与姿态参数之间的关系,
$ \begin{equation} \begin{bmatrix} \pmb {R_u} \\ \pmb {R_v} \end{bmatrix} =M{\pmb B} \end{equation} $
(18) $ \begin{equation} M= \begin{bmatrix} \pmb {R_u} \\ \pmb {R_v} \end{bmatrix} {\pmb B}^{\rm T}({\pmb B}{\pmb B}^{\rm T})^{-1} \end{equation} $
(19) 则$M$即是我们需要的姿态模型.通过该姿态模型, 我们可以使用形状参数直接求出对应的投影姿态参数.给定一幅图像目标脊椎的形状参数$b$, 则其对应的姿态参数为
$ \begin{equation} \begin{bmatrix} r_u \\ r_v \end{bmatrix} =Mb \end{equation} $
(20) 1.4 配准
如图 5所示, 在术前, 针对由CT投影生成的DRR图像, 首先用AAM模型分割目标脊椎得到其形状参数, 然后建立姿态模型, 即形状参数与投影角度之间的关系; 在术中, 先对X-ray图像使用AAM模型分割目标脊椎得到形状参数, 然后通过术前得到的姿态模型求取投影参数.具体如下:
对于术中待配准的X-ray图像$I_{ \mbox{X-ray}}$, 我们使用AAM模型分割目标脊椎(需手动指定初始位置)并获得其形状参数$b_{ \mbox{X-ray}}$, 则其对应的姿态参数为
$ \begin{equation} \begin{bmatrix} r_u \\ r_v \end{bmatrix} =Mb_{ \mbox{X-ray}} \end{equation} $
(21) 获得了姿态参数后, 使用此姿态参数生成对应的DRR图像.利用生成的DRR图像和X-ray图像上标志点的几何变换关系, 我们可以求出几何参数.具体如下:
我们根据得出的姿态参数对目标CT图像$I_{\rm CT}$进行DRR投影, 得到对应的DRR图像$I_{\rm DRR}$, 有:
$ \begin{equation} I_{\rm DRR}={P(T}(I_{\rm CT};r_u, r_v, 0, r_0, 0, 0)) \end{equation} $
(22) $x_{ \mbox{X-ray}}$是$I_{\mbox{X-ray}}$中一点(齐次坐标下), $x_{\rm DRR}$是$I_{\rm DRR}$中的$x_{ \mbox{X-ray}}$的对应点(齐次坐标下).
$ \begin{equation} x_{ \mbox{X-ray}}=kRSx_{\rm DRR} \end{equation} $
(23) 对于$I_{\mbox{X-ray}}$中目标脊椎的标志点的点集为$X_{ \mbox{X-ray}}$, 和$I_{\rm DRR}$中目标脊椎的标志点的点集为$X_{\rm DRR}$. $X_{ \mbox{X-ray}}$的重心在二维投影平面的坐标为$(cx, cy)$; 由于CT中目标脊椎的中心在投影初始位置, 所以我们可以通过$X_{ \mbox{X-ray}}$重心的位置求出$\theta$和$\phi$,
$ \begin{equation} \theta ={\rm arctan}\left(-\frac{cx}{{h}}\right), \quad \phi={\rm arctan}\left(\frac{cy}{{h}}\right) \end{equation} $
(24) 通过$\theta$和$\phi$我们可以得到$R$, 于是我们可以消除球面旋转的影响:
$ \begin{equation} k^{-1}R^{-1}x_{ \mbox{X-ray}}=Sx_{\rm DRR} \end{equation} $
(25) 此时, 我们只需要求出相似矩阵$S$的旋转系数和放缩系数就可以求出X-ray图像与CT的配准关系.我们使用以下目标函数来求相似矩阵$S$的旋转系数$r_z$和放缩系数$s$.
$ \begin{equation} \begin{aligned} (r_z, s)= \arg \min\limits_{(r_z, s)}\left(\sum\limits_{i=1}^{n}\parallel {k_i}^{-1}R^{-1}x_i-Sy_i\parallel \right), \\ x_i\in X_{ \mbox{X-ray}}, \ y_i\in X_{\rm DRR} \end{aligned} \end{equation} $
(26) 得到$(r_z, s)$之后, 我们可以使用$s$和$r_0$求出$\delta r$
$ \begin{equation} \frac{r_0}{(r_0+\Delta r)}=s\Rightarrow \Delta r=\frac{r_0(1-s)}{s} \end{equation} $
(27) 这样我们就求出了和X-ray相对应的DRR图像的所有投影参数, 即完成了配准.
2. 实验
2.1 实验数据和实验环境
CT数据由北京医院提供. CT采集设备为GE公司的Discovery HD720, CT数据分辨率为0.24 mm × 0.24 mm × 0.7 mm.有6组CT数据和与其对应的冠状面X光图像, 构建统计形状模型时, 本文又同时使用没有对应图像的另外5个CT数据和20个X-ray冠状面图像.处理数据和运行算法是在一台个人电脑上进行的, 配置为Intel(R) Core(TM) i5-2400 CPU @ 3.10 GHz, 4 GB内存.运行算法平台为Matlab R2014b.
2.2 生成DRR投影图像
对于有6组有对应冠状面X-ray图像的CT图像, 本文使用式(7)所示的投影方式, 投影参数$r_u\in(-5^\circ , 5^\circ) $, $r_v\in(-10^\circ , 10^\circ )$, 且以$1°$为间隔, 其他参数$r_w\in(-45^\circ , 45^\circ )$, $\Delta r\in(-50 mm, 50 mm)$, $\theta \in(-10^\circ , 10^\circ )$, $\phi \in(-10^\circ , 10^\circ )$, 在区间内随机指定, 每个CT投影生成$11 \times 21=231$张图像.对于没有对应冠状面X-ray图像的CT, 本文投影参数的范围控制在$r_u\in(-5^\circ , 5^\circ )$, $r_v\in(-10^\circ , 10^\circ )$, $r_w\in(-45^\circ , 45^\circ )$, $\Delta r\in(-50 mm, 50 mm)$, $\theta \in(-10^\circ , 10^\circ )$, $\phi \in(-10^\circ , 10^\circ )$, 在这个投影参数空间中随机投影生成15张DRR图像.在进行DRR投影时, 投影源到投影平面的距离$h=1 000$ mm, 投影对象的初始距离$r_0=500$ mm.
2.3 实验过程
为了充分利用数据, 我们对6组有配套CT和X-ray图像的数据使用留一交叉验证.每次我们使用这6组数据中的5组作为训练集, 剩下的一组作为测试集.我们使用训练集的5组数据和没有对应图像的另外5个CT和20个X-ray数据来建立AAM模型, 使用测试集的CT数据来建立姿态模型, 使用测试集的X-ray数据来与测试集的CT数据进行配准来验证本文方法的性能.
在建立AAM模型时, 本文从每个CT投影生成的DRR图像中随机不重复的抽取15张图像, 并和其他的X-ray图像一起建立AAM模型, 这样用来建立AAM模型的图像共有$(5+5) \times 15+5+20=175$幅图像.我们对每幅图像手动提取93个标志点, 如图 2所示.
在建立姿态模型时, 本文使用测试集的CT投影生成的DRR图像来建立姿态模型.同时为了比较线性模型和更高阶模型如二次、三次、四次模型, 本文也做了对比实验.为了比较$r_u$和$rv$在不同采样间隔下建立的姿态模型的性能, 本文也对1°、2°、3°采样间隔下建立的姿态模型做了对比.
2.4 评价准则
对于最终的配准性能的评价, 本文使用平均目标误差(Mean target register error, mTRE).对X-ray图像和配准得到的其对应的DRR图像, 手动分割出目标脊椎的轮廓, 衡量两个轮廓之间的误差来衡量配准的性能.若$G$为X-ray图像的脊椎轮廓点集, $H$为配准得到的DRR图像的脊椎轮廓的点集, 则$G$和$H$的mTRE为
$ \begin{equation} \begin{aligned} m(G, H)=\frac{\sum\limits_{i=1}^{n}{\rm min}_{j=1}^{m}d(g_i, h_j)}{n}, \\ g_i\in G, h_j\in H \end{aligned} \end{equation} $
(28) 其中, $d(g_i, h_j)$为$g_i$和$h_j$的欧氏距离.
3. 结果
图 6(a)和(b)展示了在建立姿态模型时, 分别使用线性、二次、三次和四次的模型在采样间隔为1°和2°时对$r_u$和$r_v$进行拟合时的预测误差. 图 6(c)和(d)展示了使用线性模型时, 训练样本使用1°、2°、3°采样间隔的$r_u$和$r_v$来进行拟合时的$r_u$和$r_v$的预测误差.其表明相比之下在1°采样间隔和使用线性模型来建立姿态模型时, 具有较好的性能.
图 6 线性和高阶拟合((a)和(b))与不同采样间隔下预测误差的变化((c)和(d))Fig. 6 The difference of prediction error between linear model and high order model (a), (b) and by difference sampling intervals (c), (d)图 7是配准结果, 第一行是每个病人的X-ray图像, 黑线是目标脊椎的轮廓; 第二行是配准后对应的DRR图像, 白线是目标脊椎的轮廓; 第三行是配准结果, 底图是X-ray图像, 黑线是X-ray图像中目标脊椎的轮廓, 白线是DRR中目标脊椎轮廓对应到X-ray图像中的显示.
表 1是每组CT在采样间隔为1°和使用线性模型下的姿态预测误差, 配准的平均轮廓距离和配准(包含分割)所耗费时间, 其中可以看出本文的方法精度较高, 实时性好. 表 2为本文方法与其他方法在配准精度和时间上的对比, 可以看出本文方法具有一定的优越性.
表 1 配准结果Table 1 Results of registration对象 姿态误差ru(°) 姿态误差rv(°) mTRE (mm) 时间(s) PA1 0.92±0.69 0.88±0.71 0.88±0.73 0.96 PA2 0.62±0.51 0.70±0.62 1.13±0.75 0.88 PA3 0.52±0.44 0.70±0.58 1.01±0.62 0.88 PA4 1.43±1.05 1.13±0.92 0.77±0.58 0.89 PA5 0.78±0.61 0.62±0.48 0.73±0.45 0.88 PA6 0.76±0.63 0.81±0.64 0.68±0.46 0.88 平均 0.84 0.81 0.87 0.90 表 2 各种方法对比Table 2 Comparison with other methods作者 方法框架 相似度度量 mTRE (mm) 时间(s) Russakof 基于搜索 互信息 1.3 - Russakof 基于搜索 交叉相关 1.5 - Russakof 基于搜索 梯度相关 1.3 - Russakof 基于搜索 灰度模式 1.6 - Russakof 基于搜索 梯度差 1.3 - Russakof 基于搜索 Diff.图像熵 1.9 - Otake 基于搜索 NGI - 6.3 ~ 54 Philipp 基于学习 纹理 1.05 0.02 本文 基于学习 形状 0.87 0.90 4. 讨论
如图 6所示, 在建立姿态模型时, 本文同时实验了使用线性、二次、三次、四次的模型来拟合姿态模型, 但是其预测结果却并不如简单的线性模型好, 说明形状参数与姿态参数之间具有较好的线性关系, 使用高次的模型反而容易过拟合.同时我们测试了在线性模型下使用不同的采样间隔的预测性能, 在测试范围内的趋势为采样越密集模型的预测性能就越好, 在采样间隔为1°时既能有较好的预测性能又不用生成过多的投影图像.在1°采样间隔下, 使用线性模型的预测平均误差$r_u$仅为0.84°, $r_v$仅为0.81° (表 1), 这说明了用线性模型来回归学习形状参数和姿态参数的关系是有效的.因此本文配准采用的姿态模型为1°采样间隔和线性回归学习下的模型.
表 1展示了拟合姿态模型的误差和配准误差, 可以看出本文使用学习的策略来预测投影姿态的角度误差在0.5°度到1.4°度之间, 平均预测误差$r_u$为0.84°, $r_v$为0.81°.其中第4组数据的误差比较大, 主要在于第4组数据的图像质量明显不如其他的几组数据, 因此其角度误差有明显增大.若除去第4组数据, 投影姿态角度预测误差在0.5°到0.9°之间, 平均为0.72°和0.74°.配准误差在0.6 mm ~ 1.2 mm之间, 平均0.87 mm, 配准速度平均为0.9 s, 可以看出本方法具有精度较高.传统的基于搜索策略的2D/3D配准, 搜索空间的复杂度为O($n^6$), 很难达到实时配准, 而本文的方法仅需要0.9 s, 能够满足实际应用的实时配准需求.
总体来说, 本文使用机器学习的方法, 通过建立姿态模型, 即形状参数与投影角度之间的关系, 来进行2D/3D配准, 避免了繁重的搜索.在计算投影参数时, 使用机器学习和几何变换相结合的方法, 使用几何变换的方法计算出6个投影参数中的4个, 使用机器学习的方法学习剩余的两个, 大大减小了要学习的参数空间.因此, 本方法具有实时性好, 准确性高, 鲁棒性强的优点.本文的配准方法在普通PC配置, 没有GPU加速, 以及使用计算效率并不高的MATLAB且并未对代码进行太多优化的情况下依然能够在1 s以内完成配准, 完全可以达到实时配准.
在建立DRR图像与投影参数的关系时, 本文并没有使用DRR图像的灰度信息作为学习的对象, 而是使用了形状信息, 由于形状信息与投影参数有非常好的线性相关性, 所以能够得到较好的配准结果.在学习投影参数时, 本文使用了新的投影方式, 使直接的投影图像空间和需要定位标志点的图像空间均从O($n^6$)减少到了O($n^2$), 大大减少了术前的工作量.在新的投影方式下, 几何参数和姿态参数相互独立, 因此可以用几何的方法求几何参数, 用学习的方法求姿态参数, 两者之间不会交叉影响, 也使得配准更加有效率, 结果也更准确.
本文的方法是基于分割与标志点的定位之上的, 标志点定位的效果对配准的影响较大, 本文的方法时间开销也主要耗费在分割和标志点定位上, 如果分割和标志点定位能够更加准确、快速, 本文的方法也能够更准确, 实时性更好.
附录. A
本文构建的投影方式可以表示为
$ \begin{equation} I={P(T}(I_{3{\rm D}};r_u, r_v, r_w, r, \theta, \phi )) \end{equation} $
(A1) 对象的姿态坐标系(图 3(b)所示)的基底$\beta$在世界坐标系下的表示为
$ \begin{align} \begin{aligned} \beta _E= & \begin{bmatrix} u & v & w \end{bmatrix} =\nonumber\\ &\begin{bmatrix} \cos \theta & - \sin \theta \cos \phi & \sin \theta \sin \phi \\ 0 & \sin \phi & \cos \phi \\ \sin \theta & \cos \theta \cos \phi & - \cos \theta \sin \phi \end{bmatrix} \end{aligned} \end{align} $
(A2) 在实际的操作中, 由于我们可以得到X-ray投影时投影对象与X-ray光源的大致距离$r_0$, 因此对$I_3D$进行DRR投影时可令$r$的初始值为$r_0$, 而$r$的实际影值可表示为为$r_0+\Delta r$, 投影过程可以表示为
$ \begin{equation} I={P(T}(I_{3{\rm D}};r_u, r_v, r_w, r_0+\Delta r, \theta, \phi )) \end{equation} $
(A3) 由于$\Delta r\ll r_0$, 因此我们可以近似认为$\Delta r$的改变并不引起图像结构的变化.如图A1所示, 从$O$点发出的X-ray射线经过$A$点从$B$点穿出, 当$O$点移动$\Delta r$到$O'$时, X-ray射线经过$A$点从$B'$点穿出.则
$ \begin{equation} BB'=\frac{\Delta rlh}{(r-\Delta r)r} \end{equation} $
(A4) 脊椎的厚度和宽度均远远小于投影距离, 因此$l\ll r, h\ll r$, 有$BB'\approx 0$, 这样可以近似地认为放射源经过$Delta r$的移动经过$A$点在脊椎内部通过的路径并没有发生变化, 即经过$A$点成的像的灰度值没有变化.
由于我们近似地认为$\Delta r$的变化并不引起投影图像的灰度值的变化, 那么$\Delta r$的改变仅引起投影图像大小的变化(A2), 大小的变化可以使用一个放缩变换来代替.
图 A2 $\Delta r$近似等效于相似变换Fig. A2 The effect of $\Delta r$ approximate to similar transformation为了方便证明$r_w, \Delta r, \theta, \phi$的改变引起的投影图像的变化可以使用几何变换来代替, 我们将投影变换拆解成3部分(如图A 3所示):
首先, 如图A3(a)所示, 初始化投影对象的位置为球形坐标系中$r=r_0, \theta =0, \phi =0$.然后对投影对象沿$u$轴旋转$r_u$, 沿$v$轴旋转$r_v$.投影过程可以表示为
$ \begin{equation} I^a={P(T}(I_{\rm CT};r_u, r_v, 0, r_0, 0, 0 )) \end{equation} $
(A5) 如图A3所示, 在图A3(b)的基础上, 对投影对象沿$w$轴旋转$r_w$, 并沿径向方向向外移动$\Delta r$.投影过程可以表示为
$ \begin{equation} I^b={P(T}(I_{\rm CT};r_u, r_v, r_w, r_0+\Delta r, 0, 0 )) \end{equation} $
(A6) 如图A3(c)所示, 在图A3(b)的基础上, 对投影对象沿$x$轴旋转$\theta$, 然后沿$y$轴旋转$\phi$.投影过程可以表示为
$ \begin{equation} I^c={P(T}(I_{\rm CT};r_u, r_v, r_w, r_0+\Delta r, \theta, \phi )) \end{equation} $
(A7) 我们令$x^a$为$I^a$某点的坐标, $x^b$为$I^b$中$x^a$的对应点的坐标, $x^c$为$I^c$中$x^b$的对应点的坐标, 我们把二维的投影坐标系下的坐标点增广到齐次坐标系下则有$x^A={bmatrix} x^a \\ {h} {bmatrix}$, $x^B={bmatrix} x^b \\ {h} {bmatrix}$ $x^C={bmatrix} x^c \\ {h} {bmatrix}$. $h$是光源到投影平面原点的距离.
图A3(b)过程可以使用一个旋转变换和一个放缩变换来代替. $x^A$和$x^B$之间的关系可以表示为
$ \begin{equation} x^B=Sx^A \end{equation} $
(A8) 其中
$ \begin{align} \begin{aligned} &S= \begin{bmatrix} s & 0 & 0 \\ 0 & s & 0 \\ 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} \cos r_w & \sin r_w & 0 \\ - \sin r_w & \cos r_w & 0 \\ 0 & 0 & 1 \end{bmatrix} , \\ &s=\frac{r_0}{(r_0+\Delta r)} \end{aligned} \end{align} $
(A9) 图A3(c)过程可以等价为成像平面以相同的坐标轴为轴沿相反的方向旋转, 这个过程可以等价为计算机视觉中的相机纯旋转. $x^B$和$x^C$之间的关系可以表示为
$ \begin{equation} x^C=kRx^B \end{equation} $
(A10) 其中
$ \begin{align} \begin{aligned} R= &[E]_{\beta }=([\beta]_E)^{\rm T}=\beta^{\rm T} =\\ &\begin{bmatrix} \cos \theta & 0 & \sin \theta \\ - \sin \theta \cos \phi & \sin \phi & \cos \theta \cos \phi \\ \sin \theta \sin \phi & \cos \theta & - \cos \theta \sin \phi \end{bmatrix} \end{aligned} \end{align} $
(A11) $E$为世界坐标系的基底, $k$为一个平衡系数使得$x^C$的第三维为$h$.
从以上可得:
$ \begin{equation} x^C=kRSx^A \end{equation} $
(A12) 其中
$ \begin{align} \begin{aligned} &S= \begin{bmatrix} s & 0 & 0 \\ 0 & s & 0 \\ 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} \cos r_w & \sin r_w & 0 \\ - \sin r_w & \cos r_w & 0 \\ 0 & 0 & 1 \end{bmatrix} \\ &s=\frac{r_0}{(r_0+\Delta r)} \end{aligned} \end{align} $
(A13) $ \begin{equation} R= \begin{bmatrix} \cos \theta & 0 & \sin \theta \\ - \sin \theta \cos \phi & \sin \phi & \cos \theta \cos \phi \\ \sin \theta \sin \phi & \cos \theta & - \cos \theta \sin \phi \end{bmatrix} \end{equation} $
(A14) -
图 3 $\eta_{ij}$ 与其相关信息关系图
Fig. 3 Relationship among $\eta_{ij}$ and its correlative message
图 4 $\alpha_{ij}$ 与其相关信息关系图
Fig. 4 Relationship among $\alpha_{ij}$ and its correlative message
表 1 部分符号说明
Table 1 The explanation of some symbol
符号 意义 $N$ 聚类数据点个数 $M$ 同类集个数 $h_1,h_2$ 数据点 $h_1,h_2$ $c_{ij}$ 变量节点, 为0表示 $j$ 不是 $i$ 的类中心点; 为1表示 $j$ 是 $i$ 的类中心点 $E_{ij}(\cdot)$ $E_j(c_{1j},\cdots,c_{Nj})$ 数据点 $j$ 的同类约束与一致性约束函数 $\rho_{ij}$ 表示变量节点 $c_{ij}$ 向函数节点 $E_j$ 所发送的标量信息 $c_i$ 数据点 $i$ 的类中心点 $P$ 全体同类集所构成的集合 $p^i$ 数据点 $i$ 所在的同类约束集 $I_i(\cdot)$ $I_i(c_{i1},\cdots,c_{iN})$ 为数据点 $i$ 的唯一性约束函数 $\alpha_{ij}$ 表示函数节点 $E_j$ 向变量节点 $ c_{ij}$ 所发送的标量信息 $\beta_{ij}$ 表示变量节点 $c_{ij}$ 向函数节点 $I_i$ 所发送的标量信息 $p_v$ 第 $v$ 个同类集 ⊕ 异或 ${{\bar P}}$ 无同类约束的数据点集 $S_{ij}(\cdot)$ 定义在数据点 $i$ , $j$ 之间的相似度函数 $s(i,j)$ 数据点 $i$ , $j$ 之间的相似度 $\eta_{ij}$ 表示函数节点 $I_i$ 向变量节点 $c_{ij}$ 所发送的标量信息 
下载: 导出CSV
表 2 人工数据上的聚类结果参数对比
Table 2 Performance comparison on man-made dataset
Sample rate Item F-measure (%) Pure (%) (%) HCSAP SAP SSAP MPCK-MEAN DSCA HCSAP SAP SSAP MPCK-MEAN DSCA Mean 72.12 72.12 72.12 70.31 69.3 56.50 56.50 56.50 53.43 55.0 0 std (0) (0) (0) (1.3) (3.6) (0) (0) (0) (1.1) (2.1) p-value - - - 4.2E-3 6.6E-3 - - - 1.8E-1 3.4E-1 Mean 87.24 82.74 80.22 85.27 81.66 80.47 72.41 70.50 77.39 75.4 10 std (6.6) (4.7) (0.8) (5.2) (9.2) (1.7) (1.1) (2.4) (2.1) (3.7) p-value - 3.1E-2 (+) 2.2E-5 (+) 9.7E-2 6.3E-3 (+) - 3.9E-2 (+) 4.1E-5 (+) 6.4E-2 6.8E-2 Mean 96.15 80.45 81.78 90.00 88.6 95.75 72.57 73.66 90.41 76.8 20 std (1.0) (1.6) (1.8) (4.1) (4.5) (4.0) (1.6) (2.7) (0.5) (1.4) p-value - 9.4E-4 (+) 7.8E-5 (+) 9.2E-3 (+) 9.2E-3 (+) - 1.7E-7 (+) 2.3E-6 (+) 1.4E-2 (+) 7.5E-6 (+) Mean 96.24 91.24 92.47 90.36 91.33 97.58 89.00 85.74 90.06 89.6 30 std (2.0) (4.1) (5.1) (0.8) (1.6) (0.2) (6.6) (4.1) (0.2) (2.8) p-value - 4.9E-2 (+) 5.1E-2 8.4E-3 (+) 7.4E-3 (+) - 3.4E-3 (+) 9.5E-8 (+) 1.6E-2 (+) 4.7E-4 (+) Mean 96.66 88.57 87.98 90.21 89.2 97.35 88.65 86.97 90.33 90.5 40 std (1.3) (3.0) (2.7) (0.2) (4.5) (2.0) (1.2) (0.9) (0.5) (7.7) p-value - 5.7E-3 (+) 1.1E-3 (+) 6.6E-3 (+) 3.9E-3 (+) - 1.1E-4 (+) 2.4E-7 (+) 1.8E-2 (+) 7.1E-3 (+) Mean 98.05 90.34 88.84 90.70 90.8 98.25 89.65 90.45 88.87 90.0 50 std (0.2) (7.1) (1.4) (0.6) (2.3) (0.2) (2.8) (9.6) (0.7) (3.4) p-value - 5.1E-2 7.2E-4 (+) 9.0E-5 (+) 1.4E-4 (+) - 42E-4 (+) 3.7E-7 (+) 8.4E-3 (+) 6.7E-3 (+) 注:表中p-value为5 %显著性水平下的 $t$ 检验值, "+"表示HCSAP在5 %显著性水平下优于对比聚类算法."-"表示在5 %显著性水平下HCSAP劣于对比聚类算法.粗体字表示对比较优者 (下同).
下载: 导出CSV
表 3 实验数据集
Table 3 Dataset used in experiment
Item Number of instance Dimension Class Preference Optdigit 1 797 64 10 $1\times Mid$ Iris 150 4 3 $3\times Mid$ Ionosphere 351 34 2 $10\times Mid$ Letter recogni- 2 241 16 3 $1\times Mid$ tion {I, J, L} Pendigits 3 498 16 10 $1\times Mid$ glass 214 9 6 $5\times Mid$ wine 178 13 3 $5\times Mid$ wdbc 768 8 2 $50\times Mid$
下载: 导出CSV
表 4 Optdigit数据集上的聚类结果对比
Table 4 Performance comparison on Optdigit dataset
Sample rate Item F-measure (%) Pure (%) (%) HCSAP SAP SSAP MPCK-MEAN DSCA HCSAP SAP SSAP MPCK-MEAN DSCA Mean 22.35 22.35 22.35 19.14 20.61 12.57 12.57 12.57 10.68 11.46 0 std (0) (0) (0) (1.25) (3.87) (0) (0) (0) (1.6) (0.9) p-value - - - 4.3E-3 4.9E-2 - - - 4.1E-2 (+) 4.8E-2 Mean 31.86 30.03 29.30 27.98 30.41 18.97 17.75 15.34 14.68 16.35 10 std (4.69) (1.30) (2.47) (1.50) (4.94) (5.02) (5.92) (6.1) (5.7) (2.2) p-value - 3.1E-1 3.3E-1 2.6E-1 5.1E-1 - 2.7E-1 6.1E-1 1.4E-1 9.9E-2 Mean 42.57 43.15 44.63 40.55 41.55 27.10 27.71 27.96 27.30 24.63 20 std (7.4) (8.01) (6.91) (7.65) (9.52) (9.00) (3.36) (4.86) (7.96) (8.14) p-value - 2.2E-1 6.6E-1 1.0E-1 2.9E-1 - 5.7E-1 6.7E-1 4.3E-1 7.4E-2) Mean 54.41 52.5 51.23 49.87 52.44 36.61 35.78 34.79 30.76 31.87 30 std (9.02) (2.01) (4.31) (2.44) (3.75) (2.67) (0.79) (6.6) (8.2) (7.8) p-value - 2.6E-1 1.7E-1 4.6E-2 (+) 5.7E-1 - 4.3E-1 8.7E-2 4.4E-2 (+) 2.5E-2 (+) Mean 62.67 61.35 61.22 59.57 61.24 45.85 44.46 45.20 41.85 40.27 40 std (2.39) (1.71) (1.6) (4.21) (8.34) (0.86) (3.12) (4.20) (7.14) (9.48) p-value - 4.0E-1 4.3E-1 2.9E-1 1.6E-1 - 1.7E-1 2.7E-1 7.7E-2 2.1E-2 (+) Mean 71.75 68.84 68.8 69.54 69.33 56.09 52.69 51.27 48.62 50.11 50 std (9.58) (6.32) (9.96) (8.47) (10.20) (2.45) (4.79) (2.70) (5.47) (5.50) p-value - 2.4E-1 2.4E-11 8.1E-2 9.8E-2 - 1.4E-2 (+) 1.1E-1 2.5E-3 (+) 5.8E-2
下载: 导出CSV
表 5 Iris数据集的聚类结果对比
Table 5 Performance comparison on Iris dataset
Sample rate Item F-measure (%) Pure (%) (%) HCSAP SAP SSAP MPCK-MEAN DSCA HCSAP SAP SSAP MPCK-MEAN DSCA Mean 61.87 61.87 61.87 56.27 55.38 55.33 55.33 55.33 52.61 53.70 0 std (0) (0) (0) (3.1) (3.6) (0) (0) (0) (2.30) (4.81) p-value - - - 1.4E-2 2.2E-2 - - - 1.6E-1 4.8E-1 Mean 73.36 72.93 72.55 71.84 69.57 75.60 56.53 55.22 60.77 58.45 10 std (2.69) (0.93) (1.21) (6.40) (3.72) (5.3) (0.87) (4.11) (2.57) (12.72) p-value - 1.5E-4 (+) 1.3E-4 (+) 5.3E-4 (+) 2.2E-4 (+) - 1.3E-3 (+) 1.4E-3 (+) 5.6E-3 (+) 4.2E-2 (+) Mean 79.04 79.78 76.99 81.21 74.31 75.33 69.11 66.22 64.21 70.40 20 std (3.22) (8.02) (5.90) (8.3) (6.61) (7.33) (12.10) (18.9) (14.1) (11.23) p-value - 2.8E-1 1.4E-1 8.2E-1 5.4E-3 - 2.7E-1 2.3E-1 5.4E-1 9.1E-1 Mean 88.46 80.33 81.24 80.74 75.33 81.33 72.22 71.25 72.11 69.44 30 std (1.75) (9.15) (9.47) (4.4) (10.1) (2.91) (12.15) (11.41) (13.15) (10.9) p-value - 2.1E-1 3.4E-1 1.1E-2 1.2E-2 - 2.3E-1 2.0E-1 2.8E-1 1.1E-1 Mean 94.72 89.62 88.25 85.74 84.27 92.93 84.40 84.00 81.23 83.78 40 std (3.64) (3.79) (4.8) (5.9) (5.6) (5.77) (6.95) (8.3) (7.9) (9.1) p-value - 1.5E-1 4.6E-2 (+) 4.9E-1 5.9E-1 - 1.7E-1 1.1E-1 1.4E-1 2.4E-1 Mean 94.43 92.38 93.50 90.22 89.01 94.44 88.22 87.20 86.33 90.01 50 std (0.39) (1.39) (2.0) (7.1) (5.1) (0.03) (5.00) (6.89) (6.12) (10.88) p-value - 1.0E-1 1.7E-1 5.5E-1 6.4E-1 - 1.5E-1 1.2E-1 2.7E-1 1.4E-1
下载: 导出CSV
表 6 Ionosphere数据集上的聚类结果对比
Table 6 Performance comparison on Ionosphere dataset
Sample rate Item F-measure (%) Pure (%) (%) HCSAP SAP SSAP MPCK-MEAN DSCA HCSAP SAP SSAP MPCK-MEAN DSCA Mean 51.96 51.96 51.96 45.89 46.31 40.35 40.35 40.35 43.48 41.25 0 std (0) (0) (0) (5.2) (3.4) (0) (0) (0) (2.50) (1.31) p-value - - - 7.3E-1 6.9E-1 - 4.4E-1 5.2E-1 1.3E-1 2.3E-1 Mean 55.24 56.74 57.30 58.21 54.21 58.21 59.38 57.66 55.24 58.00 10 std (2.45) (7.87) (1.2) (7.2) (3.6) (7.32) (2.78) (7.27) (6.17) (5.48) p-value - 3.5E-2 (-) 4.8E-2 (-) 5.4E-1 7.9E-1 - 8.2E-1 6.3E-1 5.2E-1 4.5E-1 Mean 56.45 61.13 60.34 54.29 55.12 63.41 64.12 64.30 62.34 61.25 20 std (1.97) (2.36) (1.90) (4.87) (3.57) (5.79) (3.18) (5.54) (7.53) (4.74) p-value - 5.40E-3 (-) 3.47E-2 (-) 4.4E-1 5.1E-1 - 2.8E-1 3.5E-1 6.4E-1 4.1E-1 Mean 66.61 61.16 65.14 57.02 59.54 63.74 67.20 61.42 61.28 60.11 30 std (3.25) (5.47) (3.32) (5.42) (4.14) (5.20) (1.44) (8.54) (3.15) (7.21) p-value - 2.8E-1 4.2E-1 3.3E-1 2.4E-1 - 1.9E-1 2.9E-1 1.6E-1 1.7E-1 Mean 67.61 71.68 68.50 64.71 69.87 62.66 64.04 57.99 60.34 61.23 40 std (4.23) (3.03) (1.20) (4.56) (1.57) (8.17) (7.24) (4.8) (1.36) (5.4) p-value - 2.4E-2 (-) 3.7E-2 (-) 1.7E-1 5.6E-1 - 2.5E-1 3.6E-1 2.2E-1 1.4E-1 Mean 84.16 83.17 80.26 80.66 84.78 72.53 71.33 72.55 70.21 69.88 50 std (6.12) (4.87) (2.80) (2.69) (4.31) (5.60) (7.53) (5.33) (2.42) (4.69) p-value - 3.6E-1 3.4E-1 4.7E-1 2.1E-1 - 1.9E-1 3.9E-1 2.2E-1 1.0E-1
下载: 导出CSV
表 7 Letter-recognition {I, J, L}上的聚类结果对比
Table 7 Performance comparison on Letter-recognition dataset
Sample rate Item F-measure (%) Pure (%) (%) HCSAP SAP SSAP MPCK-MEAN DSCA HCSAP SAP SSAP MPCK-MEAN DSCA Mean 49.87 49.87 49.87 41.30 42.33 33.33 33.33 33.33 31.54 30.36 0 std (0) (0) (0) (1.9) (4.1) (0) (0) (0) (2.5) (3.1) p-value - - - 5.7E-2 6.9E-2 - - - 1.7E-1 1.0E-1 Mean 54.42 55.01 54.36 55.11 57.21 39.00 38.10 40.23 39.98 40.05 10 std (8.90) (2.63) (5.7) (6.4) (3.89) (8.08) (2.78) (1.4) (2.0) (3.7) p-value - 6.2E-1 2.1E-1 4.8E-1 1.2E-1 - 2.3E-1 5.6E-1 7.4E-1 6.1E-1 Mean 59.47 52.01 51.69 57.20 55.31 42.66 35.33 34.88 37.90 35.87 20 std (1.92) (5.73) (4.8) (6.8) (5.0) (9.57) (7.26) (5.8) (3.2) (2.8) p-value - 4.2E-2 (+) 3.2E-2 (+) 1.1E-1 3.1E-1 - 4.9E-2 2.3E-2 4.7E-2 2.6E-2 Mean 67.90 65.36 66.30 64.87 60.45 52.66 50.00 49.68 50.33 51.74 30 std (0.41) (6.44) (3.2) (5.6) (4.9) (1.84) (1.54) (1.74) (2.53) (3.40) p-value - 2.6E-1 3.0E-1 1.7E-1 2.6E-1 - 2.3E-1 1.2E-1 2.9E-1 5.4E-1 Mean 77.05 72.97 73.33 71.4 70.24 64.66 60.00 59.40 58.67 51.77 40 std (2.00) (4.43) (1.5) (2.6) (2.4) (8.17) (4.26) (7.26) (8.11) (14.25) p-value - 3.3E-1 4.2E-1 1.1E-1 1.5E-1 - 3.4E-1 2.9E-1 4.1E-1 5.3E-1 Mean 84.16 83.17 84.12 83.00 81.47 73.33 71.33 70.11 68.25 67.49 50 std (4.55) (7.41) (5.4) (4.9) (4.4) (2.62) (7.53) (5.1) (7.6) (5.3) p-value - 4.9E-1 5.0E-1 2.3E-1 2.3E-1 - 3.3E-1 2.8E-1 1.0E-1 4.4E-2 (+)
下载: 导出CSV
表 8 Pendigits数据集的聚类结果对比
Table 8 Performance comparison on Pendigits dataset
Sample rate Item F-measure (%) Pure (%) (%) HCSAP SAP SSAP MPCK-MEAN DSCA HCSAP SAP SSAP MPCK-MEAN DSCA Mean 19.23 19.23 19.23 17.21 16.32 11.20 11.20 11.20 9.79 9.64 0 std (0) (0) (0) (1.42) (2.51) (0) (0) (0) (0.25) (0.36) p-value - - - 9.4E-3 (+) 2.8E-3 (+) - - - 3.9E-2 (+) 2.8E-2 (+) Mean 27.40 23.17 24.65 24.68 21.97 16.72 13.75 12.99 13.58 11.95 10 std (1.38) (8.62) (7.64) (9.17) (4.11) (5.03) (3.15) (2.87) (2.77) (1.44) p-value - 2.3E-1 5.6E-2 2.8E-1 5.8E-2 - 4.1E-1 9.6E-2 6.7E-1 6.1E-1 Mean 38.66 35.19 34.67 33.74 34.21 36.14 25.58 24.71 21.95 27.64 20 std (0.88) (3.67) (4.25) (5.50) (6.67) (3.13) (8.79) (3.34) (5.61) (4.13) p-value - 5.6E-1 2.4E-1 2.7E-1 3.1E-1 - 8.3E-3 2.3E-3 9.8E-4 1.9E-3 Mean 60.54 57.56 55.82 51.64 56.83 46.19 43.08 40.27 39.87 41.56 30 std (9.90) (0.26) (1.13) (4.21) (6.57) (0.54) (2.86) (3.41) (4.12) (3.49) p-value - 8.3E-1 5.3E-1 5.6E-2 6.6E-1 - 5.8E-1 4.1E-1 8.6E-2 2.9E-1 Mean 68.49 62.12 63.77 60.16 62.57 55.46 48.51 44.21 39.48 41.67 40 std (1.28) (5.29) (6.84) (3.46) (4.57) (6.09) (1.93) (1.53) (4.85) (3.34) p-value - 5.6E-1 6.8E-1 4.9E-1 1.4E-1 - 4.6E-2 (+) 5.3E-3 (+) 2.1E-4 (+) 9.4E-3 (+) Mean 75.75 66.30 67.38 67.22 64.14 65.23 53.60 54.69 55.21 53.96 50 std (4.58) (8.38) (7.52) (7.31) (5.63) (2.58) (6.82) (7.39) (4.61) (9.42) p-value - 6.1E-2 7.6E-1 4.9E-1 2.0E-1 - 3.8E-2 (+) 4.2E-2 (+) 1.6E-2 (+) 6.4E-3 (+)
下载: 导出CSV
表 9 glass数据集的聚类结果对比
Table 9 Performance comparison on glass dataset
Sample rate Item F-measure (%) Pure (%) (%) HCSAP SAP SSAP MPCK-MEAN DSCA HCSAP SAP SSAP MPCK-MEAN DSCA Mean 31.02 31.02 31.02 28.66 27.14 31.66 31.66 31.66 28.51 30.69 0 std (0) (0) (0) (2.80) (3.74) (0) (0) (0) (1.90) (2.45) p-value - - - 2.63E-1 1.77E-1 - - - 2.1E-1 2.6E-1 Mean 37.24 35.85 35.62 31.89 33.57 38.00 38.00 37.15 35.46 34.76 10 std (8.90) (3.17) (4.66) (5.78) (9.51) (8.08) (2.78) (3.64) (5.21) (4.23) p-value - 6.0E-1 3.4E-1 1.9E-1 2.4E-1 - 8.4E-1 5.6E-1 3.6E-1 3.1E-1 Mean 40.98 37.80 35.70 36.44 37.15 42.66 35.33 34.36 31.93 32.19 20 std (0.06) (0.02) (0.08) (1.62) (3.48) (9.57) (7.26) (6.19) (8.42) (2.96) p-value - 1.1E-1 6.4E-2 8.3E-2 4.8E-1 - 5.4E-2 4.9E-2 (+) 2.5E-2 (+) 3.4E-2 (+) Mean 46.05 43.32 44.22 40.35 45.11 70.87 54.52 55.21 52.94 57.14 30 std (0.15) (3.21) (3.90) (5.44) (7.16) (1.50) (6.36) (4.83) (8.91) (7.88) p-value - 2.9E-1 5.2E-1 9.7E-2 4.5E-1 - 4.6E-2 (+) 2.0E-2 (+) 9.4E-3 (+) 5.6E-2 Mean 53.23 47.71 46.25 42.18 47.84 80.06 61.06 64.37 59.81 60.56 40 std (1.46) (5.89) (4.77) (4.65) (7.21) (5.00) (7.27) (8.36) (7.24) (4.98) p-value - 1.8E-1 1.3E-1 7.6E-2 5.5E-1 - 5.7E-2 1.7E-1 8.7E-3 (+) 7.68E-2 Mean 54.67 50.70 51.28 49.57 51.14 79.63 64.02 61.44 62.37 59.87 50 std (7.43) (4.98) (6.40) (7.15) (8.44) (8.83) (5.42) (6.48) (7.21) (9.18) p-value - 1.6E-1 3.6E-1 7.4E-2 6.1E-1 - 5.0E-2 (+) 4.4E-2 (+) 4.5E-2 (+) 6.9E-3 (+)
下载: 导出CSV
表 10 wine数据集的聚类结果对比
Table 10 Performance comparison on wine dataset
Sample rate Item F-measure (%) Pure (%) (%) HCSAP SAP SSAP MPCK-MEAN DSCA HCSAP SAP SSAP MPCK-MEAN DSCA Mean 60.21 60.21 60.21 54.39 57.82 70.54 70.54 70.54 64.87 61.49 0 std (0) (0) (0) (5.67) (4.10) (0) (0) (0) (5.10) (6.54) p-value - - - 2.9E-1 4.6E-1 - - - 1.3E-1 9.3E-2 Mean 79.16 68.98 69.33 65.47 67.26 84.94 72.36 73.66 75.19 70.58 10 std (5.450) (3.82) (5.44) (8.21) (4.94) (8.35) (5.26) (5.87) (4.24) (6.29) p-value - 6.3E-3 (+) 9.2E-4 (+) 6.1E-3 (+) 8.1E-2 (+) - 4.7E-2 (+) 4.9E-2 (+) 6.7E-2 8.1E-3 (+) Mean 81.36 71.82 69.88 68.15 60.47 84.83 73.88 71.20 69.64 65.88 20 std (3.65) (5.49) (5.40) (8.14) (6.47) (8.22) (4.55) (6.88) (7.52) (10.37) p-value - 7.4E-2 4.8E-2 1.3E-1 9.1E-2 - 1.5E-1 8.3E-2 7.2E-2 4.3E-2 (+) Mean 84.78 83.27 80.31 81.55 82.41 92.06 89.40 85.94 90.31 88.49 30 std (2.93) (5.21) (6.40) (3.70) (7.52) (1.68) (6.34) (5.80) (1.23) (3.54) p-value - 1.8E-1 1.1E-1 3.4E-1 4.4E-1 - 1.7E-1 8.3E-2 4.6E-1 9.7E-2 Mean 90.22 84.24 80.64 81.47 72.63 95.06 89.66 88.33 90.27 87.92 40 std (2.81) (3.51) (4.36) (1.42) (0.99) (1.51) (5.82) (6.42) (8.66) (9.11) p-value - 4.0E-2 (+) 2.2E-3 (+) 3.6E-2 (+) 9.4E-3 (+) - 1.3E-1 8.4E-2 5.2E-2 4.3E-2 (+) Mean 89.76 86.68 85.85 80.74 81.69 88.82 85.74 85.63 84.22 80.75 50 std (1.99) (4.99) (6.41) (6.28) (7.11) (2.62) (7.53) (8.90) (7.24) (9.11) p-value - 2.7E-1 2.0E-1 5.7E-2 3.3E-1 - 2.7E-1 1.1E-1 3.4E-1 2.1E-1
下载: 导出CSV
表 11 wdbc数据集的聚类结果对比
Table 11 Performance comparison on wdbc dataset
Sample rate Item F-measure (%) Pure (%) (%) HCSAP SAP SSAP MPCK-MEAN DSCA HCSAP SAP SSAP MPCK-MEAN DSCA Mean 52.31 52.31 52.31 48.42 47.49 55.74 55.74 55.74 51.78 52.69 0 std (0) (0) (0) (1.10) (1.67) (0) (0) (0) (0.62) (0.37) p-value - - - 4.5E-2 (+) 3.1E-2 (+) - - - 4.8E-2 (+) 5.7E-2 Mean 66.35 50.72 48.39 51.46 49.21 61.39 47.80 47.92 44.91 51.68 10 std (13.38) (1.42) (2.82) (2.6) (5.06) (11.73) (3.50) (6.41) (17.46) (14.25) p-value - 1.5E-1 9.2E-2 3.4E-1 1.1E-1 - 1.2E-1 2.4E-1 4.2E-1 2.9E-1 Mean 74.27 66.58 67.24 64.21 60.37 72.16 61.16 60.58 57.26 59.34 20 std (13.78) (14.87) (11.35) (15.87) (9.58) (14.45) (17.51) (15.68) (11.34) (8.48) p-value - 5.0E-1 6.2E-1 9.8E-2 4.1E-1 - 4.1E-1 5.4E-1 1.2E-1 2.6E-1 Mean 85.90 59.10 58.22 57.31 56.74 84.23 52.42 50.72 48.64 51.77 30 std (0. 86) (17.4) (20.55) (8.27) (4.90) (1.26) (4.28) (5.60) (4.89) (2.77) p-value - 9.0E-03 (+) 2.5E-2 (+) 5.1E-3 (+) 6.4E-3 (+) - 7.4E-04 (+) 5.6E-5 (+) 4.9E-6 (+) 1.8E-7 (+) Mean 88.09 71.83 71.27 69.58 64.96 87.39 70.61 71.33 64.99 68.41 40 std (1.35) (8.86) (7.89) (10.54) (9.73) (3.0) (8.14) (6.64) (10.37) (12.85) p-value - 4.70E-2 (+) 2.8E-2 (+) 4.2E-3 (+) 7.7E-3 (+) - 5.3E-2 5.1E-2 4.8E-3 (+) 2.5E-2 (+) Mean 87.53 84.82 84.32 81.62 82.44 88.32 84.74 80.16 75.32 72.19 50 std (7.18) (9.02) (10.33) (8.27) (9.11) (7.80) (9.83) (8.12) (10.77) (11.65) p-value - 4.8E-2 (+) 3.4E-2 (+) 8.9E-3 (+) 7.7E-3 (+) - 4.1E-2 (+) 2.2E-2 (+) 3.6E-2 (+) 1.8E-2 (+)
下载: 导出CSV
-
[1] Frey B J, Dueck D. Clustering by passing messages between data points. Science, 2007, 315(5814):972-976 doi: 10.1126/science.1136800 [2] 许晓丽, 卢志茂, 张格森, 李纯, 张琦.改进近邻传播聚类的彩色图像分割.计算机辅助设计与图形学学报, 2012, 24(4):514-519 http://www.cnki.com.cn/Article/CJFDTOTAL-JSJF201204015.htmXu Xiao-Li, Lu Zhi-Mao, Zhang Ge-Sen, Li Chun, Zhang Qi. Color image segmentation based on improved affinity propagation clustering. Journal of Computer-Aided Design & Computer Graphics, 2012, 24(4):514-519 http://www.cnki.com.cn/Article/CJFDTOTAL-JSJF201204015.htm [3] Borile C, Labarre M, Franz S, Sola C, Refrégier G. Using affinity propagation for identifying subspecies among clonal organisms:lessons from M. tuberculosis. BMC Bioinformatics, 2011, 12:224 doi: 10.1186/1471-2105-12-224 [4] 储岳中, 徐波, 高有涛, 邰伟鹏.基于近邻传播聚类与核匹配追踪的遥感图像目标识别方法.电子与信息学报, 2014, 36(12):2923-2928 http://www.cnki.com.cn/Article/CJFDTOTAL-DZYX201412021.htmChu Yue-Zhong, Xu Bo, Gao You-Tao, Tai Wei-Peng. Technique of remote sensing image target recognition based on affinity propagation and kernel matching pursuit. Journal of Electronics and Information Technology, 2014, 36(12):2923-2928 http://www.cnki.com.cn/Article/CJFDTOTAL-DZYX201412021.htm [5] 王开军, 张军英, 李丹, 张新娜, 郭涛.自适应仿射传播聚类.自动化学报, 2007, 33(12):1242-1246 http://www.aas.net.cn/CN/abstract/abstract15756.shtmlWang Kai-Jun, Zhang Jun-Ying, Li Dan, Zhang Xin-Na, Guo Tao. Adaptive affinity propagation clustering. Acta Automatica Sinica, 2007, 33(12):1242-1246 http://www.aas.net.cn/CN/abstract/abstract15756.shtml [6] 刘建伟, 刘媛, 罗雄麟.半监督学习方法.计算机学报, 2015, 38(8):1592-1617Liu Jian-Wei, Liu Yuan, Luo Xiong-Lin. Semi-supervised learning methods. Chinese Journal of Computers, 2015, 38(8):1592-1617 [7] Bijral A S, Ratliff N, Srebro N. Semi-supervised learning with density based distances.[Online], available:http://ttic.uchicago.edu/~nati/Publications/SemiSupDBD.pdf, October 10, 2014 [8] Wagstaff K, Cardie C. Clustering with instance-level constraints. In:Proceedings of the 17th International Conference on Machine Learning (ICML2000). Stanford:Morgan Kaufmann Publishers, 2000. 1103-1110 [9] 肖宇, 于剑.基于近邻传播算法的半监督聚类.软件学报, 2008, 19(11):2803-2813 http://www.cnki.com.cn/Article/CJFDTOTAL-RJXB200811005.htmXiao Yu, Yu Jian. Semi-supervised clustering based on affinity propagation algorithm. Journal of Software, 2008, 19(11):2803-2813 http://www.cnki.com.cn/Article/CJFDTOTAL-RJXB200811005.htm [10] 张震, 汪斌强, 伊鹏, 兰巨龙.一种分层组合的半监督近邻传播聚类算法.电子与信息学报, 2013, 35(3):645-651 http://www.cnki.com.cn/Article/CJFDTOTAL-DZYX201303020.htmZhang Zhen, Wang Bin-Qiang, Yi Peng, Lan Ju-Long. Semi-supervised affinity propagation clustering algorithm based on stratified combination. Journal of Electronics and Information Technology, 2013, 35(3):645-651 http://www.cnki.com.cn/Article/CJFDTOTAL-DZYX201303020.htm [11] 张建朋, 陈福才, 李邵梅, 刘力雄.基于密度与近邻传播的数据流聚类算法.自动化学报, 2014, 40(2):277-288 http://www.aas.net.cn/CN/abstract/abstract16309.shtmlZhang Jian-Peng, Chen Fu-Cai, Li Shao-Mei, Liu Li-Xiong. Data stream clustering algorithm based on density and affinity propagation techniques. Acta Automatica Sinica, 2014, 40(2):277-288 http://www.aas.net.cn/CN/abstract/abstract16309.shtml [12] Givoni I E, Frey B J. Semi-supervised affinity propagation with instance-level constraints. In:Proceedings of the 12th International Conference on Artificial Intelligence and Statistics (AISTATS). Clearwater Beach, Florida, USA:JMLR W & CP5, 2009. 161-168 [13] 赵宪佳, 王立宏.近邻传播半监督聚类算法的分析与改进.计算机工程与应用, 2010, 46(36):168-170 http://www.cnki.com.cn/Article/CJFDTOTAL-JSGG201036047.htmZhao Xian-Jia, Wang Li-Hong. Analysis and improvement of semi-supervised clustering algorithm based on affinity propagation. Computer Engineering and Applications, 2010, 46(36):168-170 http://www.cnki.com.cn/Article/CJFDTOTAL-JSGG201036047.htm [14] Wagstaff K, Cadrie C, Rogers S, Schroedl S. Constrained K-means clustering with background knowledge. In:Proceedings of the 18th International Conference on Machine Learning (ICML2001). Williamstown:Morgan Kaufmann Publishers, 2001. 577-584 [15] 尹学松, 胡恩良, 陈松灿.基于成对约束的判别型半监督聚类分析.软件学报, 2008, 19(11):2791-2802 http://www.cnki.com.cn/Article/CJFDTOTAL-RJXB200811004.htmYin Xue-Song, Hu En-Liang, Chen Song-Can. Discriminative semi-supervised clustering analysis with pairwise constraints. Journal of Software, 2008, 19(11):2791-2802 http://www.cnki.com.cn/Article/CJFDTOTAL-RJXB200811004.htm [16] Kschischang F R, Frey B J, Loeliger H A. Factor graphs and the sum-product algorithm. IEEE Transactions on Information Theory, 2001, 47(2):498-519 doi: 10.1109/18.910572 [17] Weiss Y, Freeman W T. On the optimality of solutions of the max-product belief-propagation algorithm in arbitrary graphs. IEEE Transactions on Information Theory, 2001, 47(2):736-744 doi: 10.1109/18.910585 [18] Givoni I E, Frey B J. A binary variable model for affinity propagation. Neural Computation, 2009, 21(6):1589-1600 doi: 10.1162/neco.2009.05-08-785 期刊类型引用(11)
1. 王治和，常筱卿，杜辉. 基于万有引力的自适应近邻传播聚类算法. 计算机应用. 2021(05): 1337-1342 . 
百度学术2. 邱保志，张瑞霖，李向丽. 基于过滤模型的聚类算法. 控制与决策. 2020(05): 1091-1101 . 百度学术3. 征察，吉立新，高超，李邵梅，吴翼腾. 基于成对约束的偏标记数据消歧算法. 自动化学报. 2020(07): 1367-1377 . 本站查看4. 钱雪忠，王卫涛. 多维空间可调整的近邻传播聚类算法. 计算机科学与探索. 2019(01): 116-127 . 百度学术5. 曹愈远，张博文，李艳军. AP聚类改进免疫算法用于航空发动机故障诊断. 航空动力学报. 2019(08): 1795-1804 . 百度学术6. 刘璧钺，赵章焰. 基于改进LSD和AP聚类的路径边缘识别策略. 图学学报. 2019(05): 915-924 . 百度学术7. 刘自豪，张斌，祝宁，唐慧林. 基于改进AP聚类算法的自学习应用层DDoS检测方法. 计算机研究与发展. 2018(06): 1236-1246 . 百度学术8. 赵昱，陈琴，苏一丹，陈慧姣. 基于邻域相似度的近邻传播聚类算法. 计算机工程与设计. 2018(07): 1883-1888 . 百度学术9. 王卫涛，钱雪忠，曹文彬. 自适应参数调整的近邻传播聚类算法. 小型微型计算机系统. 2018(06): 1305-1311 . 百度学术10. 李晓庆，唐昊，司加胜，苗刚中. 面向混合属性数据集的改进半监督FCM聚类方法. 自动化学报. 2018(12): 2259-2268 . 本站查看11. 陈雷，肖创柏，禹晶，王真理，李学良. 基于相似性传播聚类与主成分分析的断层识别方法. 石油地球物理勘探. 2017(04): 826-833+627-628 . 百度学术其他类型引用(9)
-
下载:
计量
- 文章访问数: 2572
- HTML全文浏览量: 257
- PDF下载量: 968
- 被引次数: 20
