论文部分内容阅读
【摘 要】Mercer核技术将实际问题通过非线性变换转换到高维特征空间，提高了模式的可分性，解决了维数灾难问题。但是，未经过优化的核聚类算法不能有效地解决实际问题，如医学图像分割。为了提高核聚类算法速度，人们提出了不同的优化方法。结合KFCM-I的聚类效果及KFCM-II的效率，本文提出了一种基于精简集的快速核聚类算法，该方法优于相关算法，并应用在了MRI图像分割上。通过对MRI脑Phantom图像的分割结果表明，該方法不但提高了核聚类算法的计算复杂度，并且通过参数调整达到较好的分割效果。
【关键词】核聚类算法 高斯核参数估计 图像分割 核磁共振成像
一、引言
对于脑部MRI图像分析，精确分割出不同的组织在医院研究中扮演着非常重要的角色。过去几十年，已经有很多方法应用于MRI图像的分割。在这些方法中，模糊聚类算法已经被证实为一种有效的图像分析方法[1，5]。但是，由于受随机噪声及强度偏置场的影响，利用模糊聚类算法实现图像分割仍是一项困难的工作。为了提高聚类效果，可以采用不同的改进算法。其中，Mercer核技术[3，5]具有较好的效果。该算法通过核映射将输入模式转换到高维的特征空间（称为核空间），提高了模式的可分性，并在高维特征空间中构造线性判别函数来实现输入空间中的非线性判别函数，同时巧妙地解决了维数灾难问题。核聚类算法基于上述理论，将映射模式应用于传统的聚类算法[3]。虽然该方法优于传统的方法，但是在解决实际问题中相当耗时，如MRI图像分割。为了提高核聚类算法效率，人们提出了不同的优化算法。例如，文献[5]利用原像技术替代映射数据的线性和，提出了一种改进的聚类算法，称为KFCM-II。该方法大大降低了直接核化FCM得到的KFCM-I算法的时间复杂度。
区别于文献[5]提出的算法，本文提出了一种快速的核聚类算法，表示为KFCM-III。该方法不需要所有的映射样本来表示聚类中心。通过对医学MRI图像的分割结果证明了算法的有效性。
二、FCM、KFCM-I以及KFCM-II
（一）模糊聚类算法（FCM）
FCM（Fuzzy C-Means）是一种无监督的聚类方法，可以将个输入数据（向量）聚成（）类。该方法可以通过对目标函数的最小化获得：
表明数据属于第类，并且满足。表明第类的聚类中心，并且在最小化公式（1）的过程中，表示为所有输入样本的加权和。
使用拉格朗日乘子法，对公式（1）最小化，分别求出和两个迭代方程。聚类过程是对这两个方程进行循环迭代，直到收敛。将表示为，最终被归为第类，从而将模糊聚类问题转换为一个硬分类问题。
（二）Mercer核及KFCM-I
Mercer隐含着对应一个从原始空间到一个高维核空间的映射，提高了模式的可分性。在核特征空间的模糊聚类，称为KFCM-I（核化的FCM）。该聚类方法可以通过最小化公式（1）的核化版本来实现：
式中是第类的核聚类中心。类似地，两个迭代方程可以描述如下：
因为函数是隐性的，公式（3）和（4）不能直接进行计算，需要采用另外一种求解方法。故不能通过表示成映射模式的加权和为显式得到。
Mercer核方法提供了一种巧妙地方法解决上述问题，表示为，满足如下条件：
因为公式（6）可以进行显式地展开，那么就可以避开直接计算公式（4）。聚类初始化后，可以迭代计算公式（3）和公式（6）直至收敛，将模糊聚类结果转换为一个硬分类。
从上面可以不难看出，公式（6）是整个计算过程中最复杂的部分，计算复杂度为，为迭代的次数，在大多数情况下大于10。
虽然KFCM-I提供了一种有效的聚类方法，并且可以用于解决维数灾难问题。但计算复杂度过高，很难用于实际应用中。
（三）KFCM-II及原像技术
因为公式（6）计算复杂度较高，为了提高KFCM-I的效率，需要对其简化。为了解决该问题，文献[5]通过最小化如下目标函数提出一种新的聚类算法：
KFCM-II算法基本思想是基于可以替换为，（），也就是说的原像存在。如果该假设成立， 使用拉普拉斯乘子法，迭代方程可以得到简化。
不幸的是，使用替代并不恰当。文献[3]指出对于高斯核不存在映射数据加权和的原像。原像估计技术可能对聚类模型带来一些缺陷。例如，因为在中显式获得，所以KFCM-II从特征空间退化为中对应的一个聚类。
三、KFCM-III及精简集
（一）核聚类平方扩展的简化
为了克服KFCM-II模型的缺陷，同时保持聚类的有效性。基于精简集概念，本文提出一种新的聚类方法，称为KFCM-III。
不难发现，KFCM-I和KFCM-II使用所有输入样本来表示聚类中心（参见公式（4）和（11）），但该公式并不是最优的。本文仅使用部分典型样本来表示聚类中心，我们将第类的典型样本标记为精简集，它是的一个子集。所以，对于由类组成的整体，则存在个精简集。如果我们定义如下公式，则核聚类中心可以表示为精简集中元素的线性和，。如果选择的恰当，则能得到较好的聚类结果。直观上，不应过大或者过小，并且精简集的选择应当保留足够的样本可分性。那么可以描述如下：
由公式（10）和公式（6）比较可知，KFCM-III相对KFCM-I的效率得到了大大的提高。
（二）精简集参数
从上述分析我们可以看出，KFCM-III的性能很大程度上依赖于精简集的选择是否得当。对于特定类，我们选择具有较多成员的样本作为典型集。类似于公式（7）的加权系数，我们定义系数如下：
对于核聚类，高斯核参数的估计也是一个非常重要的问题。不同于文献[5]使用的反复试验的方法，我们将设置为高斯指数函数的拐点，满足如下公式： 四、实验结果及分析
（一）合成和MRI图像分割实验
为了验证本文算法的分割效果，本文对MR Phantom图像进行了分割实验，并对实验结果进行了分析。该数据提供了定量比较分割准确性的标准分割结果，并允许在不同的噪声和偏置场[2]条件下的比较分析。
图1：利用KFCM-III对T1加权的三维MRI phantom数据的分割结果：（a）原始图像；（b）原始图像的分割结果；（c）均值滤波图像的分割结果；（d）中值滤波图像的分割结果。
实验时，目标函数中的隶属度指数取，并且为了更清楚有效地描述实验结果，我们选取像素的灰度向量作为输入模式。为了比较相关算法的性能，我们分别采用KFCM-I、KFCM-II和KFCM-III对原始图像、中值滤波图像和均值滤波图像进行分割，其中滤波模板大小为。
在第一个实验中，我们选取T1加权的3D脑部phantom 数据，将感兴趣区域分割为白质（WM）、灰质（GM）和脊髓液（CSF）。在该实验中，使用KFCM-I（未采用预分类策略）不能在合理的时间内实现对图像的分割，对于KFCM-II和KFCM-III获得相似的实验结果。
图1给出利用KFCM-III得到的三维体积冠状切片的分割结果。目标phantom大小为像素，器官组织的分辨率为. 分割区域使用不同的灰度表示。因为KFCM-II与KFCM-III具有相似的结果，图中并未给出KFCM-II的分割结果。
但是，定量比较结果表明如果精简集选择得当，相对KFCM-II，KFCM-III将得到好的结果。
表1给出利用KFCM-II和KFCM-III对三维MRI脑部phantom数据的分割精度。主要包括在不同噪声水平和不同强度的偏置场下，对原始图像、均值滤波图像及中值滤波图像的分割结果。
分割精度定义为分割正确的像素个数除以所有的像素个数。符号pnXrfY（例如pn9rf20）表示在X%和Y%偏置场下图像的分割结果。为了描述上的方便，我们在相同精简集参数下，利用KFCM-III进行分割。例如，在表1中，表明对于三个聚类类而言，精简集中数据的个数都等于30。实际上，精简集参数可以不同并且可以选择更合理一点。关于参数选择有待进一步的研究。从表1中可以看出，即使所有的参数都相同，KFCM-III仍能得到好于KFCM-II的分割结果。
（二）执行时间效率
KFCM-III的计算复杂度和时间效率依赖于精简集参数的选择。如果所有参数设置为最大，则KFCM-III转化为KFCM-I. 一般来说，KFCM-III相对KFCM-II，计算有点复杂。但是，在调整好的参数下，取得更好的分割效果。
图5给出聚类过程中一次迭代的计算时间，大约为的平方函数，验证了上述的理论分析。
五、結论
本文提出了一种基于快速核聚类算法（称为KFCM-III），并用于MRI图像的分割。提出算法使用精简集概念来加速聚类速度。本文中，KFCM-I和KFCM-II可以看着KFCM-III的两个特例，在调整好的参数下，KFCM-III性能优于KFCM-I和KFCM-II. 该提出算法不但降低了计算复杂度，并且提高了聚类效果。但是，参数的选择需要进一步的研究。通过对MRI图像分割结果表明，该方法优于相关算法，达到较好的分割效果。
参考文献：
[1] Weiling Cai， Songcan Chen， and Daoqiang Zhang. Fast and robust fuzzy C-means clustering algorithms incorporating local information for image segmentation. Pattern Recognition， 40（3）：825-838， 2007.
[2] D Louis Collins， Alex P Zijdenbos， Vasken Kollokian， John G Sled， Noor J Kabani， Colin J Holmes， and Alan C Evans. Design and construction of a realistic digital brain phantom. IEEE Transactions on Medical Imaging， 17（3）：463-468， 1998.
[3] Bernhard Scholkopf， Sebastian Mika， Chris JC Burges， Philipp Knirsch， K-R Muller， Gunnar Ratsch， and Alex J Smola. Input space versus feature space in kernel-based methods. Neural Networks， IEEE Transactions on， 10（5）：1000-1017， 1999.
[4] Uros Vovk， Franjo Pernus， and Bostjan Likar. A review of methods for correction of intensity inhomogeneity in MRI. IEEE Transactions on Medical Imaging， 26（3）：405-421， 2007.
[5] Dao-Qiang Zhang and Song-Can Chen. A novel kernelized fuzzy C-means algorithm with application in medical image segmentation. Artificial intelligence in medicine， 32（1）：37-50， 2004.
【关键词】核聚类算法 高斯核参数估计 图像分割 核磁共振成像
一、引言
对于脑部MRI图像分析，精确分割出不同的组织在医院研究中扮演着非常重要的角色。过去几十年，已经有很多方法应用于MRI图像的分割。在这些方法中，模糊聚类算法已经被证实为一种有效的图像分析方法[1，5]。但是，由于受随机噪声及强度偏置场的影响，利用模糊聚类算法实现图像分割仍是一项困难的工作。为了提高聚类效果，可以采用不同的改进算法。其中，Mercer核技术[3，5]具有较好的效果。该算法通过核映射将输入模式转换到高维的特征空间（称为核空间），提高了模式的可分性，并在高维特征空间中构造线性判别函数来实现输入空间中的非线性判别函数，同时巧妙地解决了维数灾难问题。核聚类算法基于上述理论，将映射模式应用于传统的聚类算法[3]。虽然该方法优于传统的方法，但是在解决实际问题中相当耗时，如MRI图像分割。为了提高核聚类算法效率，人们提出了不同的优化算法。例如，文献[5]利用原像技术替代映射数据的线性和，提出了一种改进的聚类算法，称为KFCM-II。该方法大大降低了直接核化FCM得到的KFCM-I算法的时间复杂度。
区别于文献[5]提出的算法，本文提出了一种快速的核聚类算法，表示为KFCM-III。该方法不需要所有的映射样本来表示聚类中心。通过对医学MRI图像的分割结果证明了算法的有效性。
二、FCM、KFCM-I以及KFCM-II
（一）模糊聚类算法（FCM）
FCM（Fuzzy C-Means）是一种无监督的聚类方法，可以将个输入数据（向量）聚成（）类。该方法可以通过对目标函数的最小化获得：
表明数据属于第类，并且满足。表明第类的聚类中心，并且在最小化公式（1）的过程中，表示为所有输入样本的加权和。
使用拉格朗日乘子法，对公式（1）最小化，分别求出和两个迭代方程。聚类过程是对这两个方程进行循环迭代，直到收敛。将表示为，最终被归为第类，从而将模糊聚类问题转换为一个硬分类问题。
（二）Mercer核及KFCM-I
Mercer隐含着对应一个从原始空间到一个高维核空间的映射，提高了模式的可分性。在核特征空间的模糊聚类，称为KFCM-I（核化的FCM）。该聚类方法可以通过最小化公式（1）的核化版本来实现：
式中是第类的核聚类中心。类似地，两个迭代方程可以描述如下：
因为函数是隐性的，公式（3）和（4）不能直接进行计算，需要采用另外一种求解方法。故不能通过表示成映射模式的加权和为显式得到。
Mercer核方法提供了一种巧妙地方法解决上述问题，表示为，满足如下条件：
因为公式（6）可以进行显式地展开，那么就可以避开直接计算公式（4）。聚类初始化后，可以迭代计算公式（3）和公式（6）直至收敛，将模糊聚类结果转换为一个硬分类。
从上面可以不难看出，公式（6）是整个计算过程中最复杂的部分，计算复杂度为，为迭代的次数，在大多数情况下大于10。
虽然KFCM-I提供了一种有效的聚类方法，并且可以用于解决维数灾难问题。但计算复杂度过高，很难用于实际应用中。
（三）KFCM-II及原像技术
因为公式（6）计算复杂度较高，为了提高KFCM-I的效率，需要对其简化。为了解决该问题，文献[5]通过最小化如下目标函数提出一种新的聚类算法：
KFCM-II算法基本思想是基于可以替换为，（），也就是说的原像存在。如果该假设成立， 使用拉普拉斯乘子法，迭代方程可以得到简化。
不幸的是，使用替代并不恰当。文献[3]指出对于高斯核不存在映射数据加权和的原像。原像估计技术可能对聚类模型带来一些缺陷。例如，因为在中显式获得，所以KFCM-II从特征空间退化为中对应的一个聚类。
三、KFCM-III及精简集
（一）核聚类平方扩展的简化
为了克服KFCM-II模型的缺陷，同时保持聚类的有效性。基于精简集概念，本文提出一种新的聚类方法，称为KFCM-III。
不难发现，KFCM-I和KFCM-II使用所有输入样本来表示聚类中心（参见公式（4）和（11）），但该公式并不是最优的。本文仅使用部分典型样本来表示聚类中心，我们将第类的典型样本标记为精简集，它是的一个子集。所以，对于由类组成的整体，则存在个精简集。如果我们定义如下公式，则核聚类中心可以表示为精简集中元素的线性和，。如果选择的恰当，则能得到较好的聚类结果。直观上，不应过大或者过小，并且精简集的选择应当保留足够的样本可分性。那么可以描述如下：
由公式（10）和公式（6）比较可知，KFCM-III相对KFCM-I的效率得到了大大的提高。
（二）精简集参数
从上述分析我们可以看出，KFCM-III的性能很大程度上依赖于精简集的选择是否得当。对于特定类，我们选择具有较多成员的样本作为典型集。类似于公式（7）的加权系数，我们定义系数如下：
对于核聚类，高斯核参数的估计也是一个非常重要的问题。不同于文献[5]使用的反复试验的方法，我们将设置为高斯指数函数的拐点，满足如下公式： 四、实验结果及分析
（一）合成和MRI图像分割实验
为了验证本文算法的分割效果，本文对MR Phantom图像进行了分割实验，并对实验结果进行了分析。该数据提供了定量比较分割准确性的标准分割结果，并允许在不同的噪声和偏置场[2]条件下的比较分析。
图1：利用KFCM-III对T1加权的三维MRI phantom数据的分割结果：（a）原始图像；（b）原始图像的分割结果；（c）均值滤波图像的分割结果；（d）中值滤波图像的分割结果。
实验时，目标函数中的隶属度指数取，并且为了更清楚有效地描述实验结果，我们选取像素的灰度向量作为输入模式。为了比较相关算法的性能，我们分别采用KFCM-I、KFCM-II和KFCM-III对原始图像、中值滤波图像和均值滤波图像进行分割，其中滤波模板大小为。
在第一个实验中，我们选取T1加权的3D脑部phantom 数据，将感兴趣区域分割为白质（WM）、灰质（GM）和脊髓液（CSF）。在该实验中，使用KFCM-I（未采用预分类策略）不能在合理的时间内实现对图像的分割，对于KFCM-II和KFCM-III获得相似的实验结果。
图1给出利用KFCM-III得到的三维体积冠状切片的分割结果。目标phantom大小为像素，器官组织的分辨率为. 分割区域使用不同的灰度表示。因为KFCM-II与KFCM-III具有相似的结果，图中并未给出KFCM-II的分割结果。
但是，定量比较结果表明如果精简集选择得当，相对KFCM-II，KFCM-III将得到好的结果。
表1给出利用KFCM-II和KFCM-III对三维MRI脑部phantom数据的分割精度。主要包括在不同噪声水平和不同强度的偏置场下，对原始图像、均值滤波图像及中值滤波图像的分割结果。
分割精度定义为分割正确的像素个数除以所有的像素个数。符号pnXrfY（例如pn9rf20）表示在X%和Y%偏置场下图像的分割结果。为了描述上的方便，我们在相同精简集参数下，利用KFCM-III进行分割。例如，在表1中，表明对于三个聚类类而言，精简集中数据的个数都等于30。实际上，精简集参数可以不同并且可以选择更合理一点。关于参数选择有待进一步的研究。从表1中可以看出，即使所有的参数都相同，KFCM-III仍能得到好于KFCM-II的分割结果。
（二）执行时间效率
KFCM-III的计算复杂度和时间效率依赖于精简集参数的选择。如果所有参数设置为最大，则KFCM-III转化为KFCM-I. 一般来说，KFCM-III相对KFCM-II，计算有点复杂。但是，在调整好的参数下，取得更好的分割效果。
图5给出聚类过程中一次迭代的计算时间，大约为的平方函数，验证了上述的理论分析。
五、結论
本文提出了一种基于快速核聚类算法（称为KFCM-III），并用于MRI图像的分割。提出算法使用精简集概念来加速聚类速度。本文中，KFCM-I和KFCM-II可以看着KFCM-III的两个特例，在调整好的参数下，KFCM-III性能优于KFCM-I和KFCM-II. 该提出算法不但降低了计算复杂度，并且提高了聚类效果。但是，参数的选择需要进一步的研究。通过对MRI图像分割结果表明，该方法优于相关算法，达到较好的分割效果。
参考文献：
[1] Weiling Cai， Songcan Chen， and Daoqiang Zhang. Fast and robust fuzzy C-means clustering algorithms incorporating local information for image segmentation. Pattern Recognition， 40（3）：825-838， 2007.
[2] D Louis Collins， Alex P Zijdenbos， Vasken Kollokian， John G Sled， Noor J Kabani， Colin J Holmes， and Alan C Evans. Design and construction of a realistic digital brain phantom. IEEE Transactions on Medical Imaging， 17（3）：463-468， 1998.
[3] Bernhard Scholkopf， Sebastian Mika， Chris JC Burges， Philipp Knirsch， K-R Muller， Gunnar Ratsch， and Alex J Smola. Input space versus feature space in kernel-based methods. Neural Networks， IEEE Transactions on， 10（5）：1000-1017， 1999.
[4] Uros Vovk， Franjo Pernus， and Bostjan Likar. A review of methods for correction of intensity inhomogeneity in MRI. IEEE Transactions on Medical Imaging， 26（3）：405-421， 2007.
[5] Dao-Qiang Zhang and Song-Can Chen. A novel kernelized fuzzy C-means algorithm with application in medical image segmentation. Artificial intelligence in medicine， 32（1）：37-50， 2004.