特征乐高：一种使用穷举聚类进行超体素聚类的体数据探索方式(FeatureLego: Volume Exploration Us…

对于体数据的探索十分困难。一方面，体数据中蕴含着丰富的特征，探索过程中容易有所遗漏。另一方面，体数据中又充斥着噪声和用户不感兴趣的区域，需要精心进行特征的提取和筛选。对于体数据进行基于特征选择的探索方式通常基于体素聚类。在以往的工作中，交互式地聚类方式，需要用户对于聚类边界进行细致的调整，给用户带了巨大的负担。而由此衍生的多重聚类（Multiple Clustering）,则通过对于聚类算法超参数的采样，获取尽可能多的聚类结果。而在此过程中，需要大量的试错式的尝试，才能得到良好的参数采样才能得到最终良好的聚类结果，同时由于采样的问题，特征的提取可能不够穷尽而导致有所遗漏。本文提出了一种基于穷举聚类的体素聚类方式，其命名而“特征乐高”，因为其在探索过程中能够提供给用户穷尽的特征聚类结果，就像基本的积木一样，用户可以有效的进行特征选择，加以组合，最终生成定制化的体数据可视化结果。

本文提出的方法主要分为两个部分，即聚类特征提取算法和交互交互式选择，其基本的流程图如下。

聚类特征提取算法包含三个层次的聚类方法。第一阶段是将体素聚类成超体素。超体素指具有相似的强度值分布的体素块，是一种更加紧致的数据表达形式。该阶段采用的算法为三维简单线性迭代聚类（3D SLIC），该算法为二维图像处理领域的算法拓展。其原理类似于K均值聚类算法，但每个聚类中仅仅辐射周围较小的领域，因此在初始化时，增添了均匀分布聚类中心和局部微调以免陷入边界的限制改进。

第二阶段则是将超体素聚类成区域。该阶段采用的算法为改进的FH聚类算法。其同样为图像处理领域FH图像聚类算法的拓展，并加入了穷举聚类的改进。基本的三维FH聚类算法思想类似于自底而上的层次聚类方式，同时采用了图聚类的思想。其将每一个超体素视为一个节点，两两连接形成一条边，边权为超体素之间的不相似度，采用卡方距离度量超体素内部强度分布的差异。算法初始将所有节点视为单个的区域，通过权重递增的方式依次考虑每一条连接两个区域的边，如果其满足以下不等式，则该边崩溃两个区域融合。该公式描述了链接两个区域的边能否在构建基于两区域的图的最小生成树过程中，能否先于两区域独立完成最小生成树的构建。同时该公式增添了一个带有超参数的松弛项，以保证初始阶段，区域的融合可以进行。

该超参数可以有力地影响算法聚类的最终结果，想要得到尽可能多样的聚类结果，需要选取不同的超参数本文观察到该算法具有单调性、递归推导性和结果的一致性，发现在当超参数的值于一定的区间内，顺序考虑每一个链接两个区域的边是否崩溃导致区域融合时，所有的决策均可相同，因此最终能够得到完全相同的聚类结果。具体来说其通过维护一个区间（初始为0到正无穷），并将左端点作为聚类算法超参数进行聚类。当算法执行过程中一条边崩溃导致区域融合时，任何大于区间左端点的值均可以导致该边崩溃，因此在此区间内所有超参数均可以保证结果相同；当算法执行过程中一条边未满足崩溃的区域融合时，可以通过更新区间的右端点，来保证当超参数取该区间内所有的值时，在该处执行同样的决策。更新的值可以通过上述区域融合条件的不等式取等号时来计算。该算法不断迭代这个更新的过程，直到计算完成，得到该参数下的聚类结果。此时，该算法给出了一个超参数取值区间，可以保证相同的聚类结果。此时考虑下一轮计算，初始维护的区间更新为上一轮区间右端点至正无穷，不断迭代计算直到所有的超体素均被聚类为同一个区域，算法结束。该算法的伪代码如下。

第三阶段则是将区域聚类成变化聚类（meta-cluster）。之所以采用变化聚类这一词汇，是因为该过程中生成的聚类的区域成员之间在原始体数据上有十分巨大的重叠关系。该阶段同样采用图聚类的方式。通过将上一阶段计算的所有超参数取值可能下的穷尽的区域聚类的结果中的每一个区域定义为一个节点，用杰卡德距离来定义节点相连的边之间的权重，来描述不同区域间的重叠程度关系。通过将这样的一个图建立最小生成树，并依据用户选定的参数删除最小生成树种所有权重大于该权重的边，最终得到的各个连接子图则各自为一个变化聚类。

基于以上的特征提取聚类算法，该方法可以得到一系列的特征候选变化聚类，特征乐高同样提供了对于用户进行交互式特征选择的帮助。下图为该方法中提出的用户特征选择和可视化面板。

首先其建立了一个树形的数据结构来保存得到的各个变化聚类。变化聚类树的每一个节点是一个变化聚类，树结构中一个节点的父节点定义为该变化聚类节点所占区域的容量最小的超集。由于该定义下，可能会出现祖先节点对于后代节点包含关系的不完整，该方法通过复制冗余节点的方式来实现修正。兄弟节点的顺序则通过其容量的大小。这可以为用户的筛选、查询提供便利。总的来说，树形结构使得用户可以通过点选节点的方式，选择变化聚类并展开最终获得其期望获得的特征区域。

该方法同样提供了筛选和查询的功能，保证用户能有效地选择其感兴趣的特征。用户可以在切片可视化视图中刷选一定的体素，算法结合用户的筛选条件在变化聚类树结构上自底而上地搜索，并返回候选的节点，用户可以进一步地选择其所需要的特征区域，并通过调节传递函数生成定制的可视化结果。

本文最后对于多种方法进行了详尽的效果比较，可以看出该方法在提取特征的完整性和特征结构保留的健全性上都有较高的优势。

总的来说，本文提出了一种完备的针对体数据的特征提取和选择的新颖探索方式，通过改进已有的聚类算法并引入穷举聚类的思想，辅之以高效的数据管理方式，能够为用户提供简单、快捷的交互体验，值得一读。

参考文献

[1] Shreeraj J , Saad N , Kaufman A E . FeatureLego: Volume Exploration Using Exhaustive Clustering of Super-Voxels[J]. IEEE Transactions on Visualization and Computer Graphics, 2018:1-1.