毕业论文整理（一）：CT图像和邻域近似随机森林

课题要求

使用树模型分割彩色图像中的目标。

主要改进了邻域近似随机森林（Neighbourhood Approximation using Randomized Forests，NAFs），还使用了依赖树（Approximating Discrete Probability Distributions with Dependence Trees，CLT）。

邻域近似随机森林NAFs

NAFs的原论文是用于医学图像分割的，它是一个框架不是一个模型，主要作用是对任意距离定义的近似最近邻检索（approximate nearest neighbour retrieval for arbitrary distances），解决的问题类似于：给定一组带Ground Truth的灰度人体侧面CT图片去训练NAFs，然后对于一幅新的CT图片（out of samples），给出CT图像中各个内脏边缘的3D分割结果。

医学图像简介

我们平时拍的CT（计算机断层扫描技术，Computed Tomography）图片原始数据并不是平面的2D图像数据，而是3D的。它是利用精准的X射线和探测器对人体的某一部位做逐层的断面扫描，采集人体截面结构的信息，再通过重建（Reconstruction）来获得数值，最后通过一定显示手段去可视化。你可以想象成CT图像会一片一片地采集2D图像，再组装成3D的。每一片图像都会有一个“厚度”，由于是物理设备，是以毫米（mm）为单位的。在这个厚度的某个像素（实际是一个小方块）里面，很可能包含不止一种组织，那么它的取值通常是这些组织取值的平均数。还有一个概念是“层距”，相邻两片的距离如果太大，就可能不是连续的影像。又因为设备的不同，每个CT图像的层厚和层距取值可能会不同，那么如果要进行机器学习，我们需要对这些图像进行配准（Register），就是把所有的CT图像数据都转换到同一个世界坐标系XYZ下，如果多了就删去，如果少了就插入，如果坐标系不一样就旋转等等，有相应的算法可以处理。最后我们规定图像像素的大小应该是几mm厚，把CT扫描的“强度值”作为“像素值”来使用，就得到了灰度图像。灰度图像的数值通常是在-2048到2048之间的，如果要可视化，需要转为0~256，因为1000和1001的灰度你是看不出来区别的。

CT图像通常以DICOM（Digital Imaging and Communications in Medicine）格式存储，分辨率为4096级。我录制了一个gif来直观地感受一下（MITK workbench打开DICOM文件）：

Patches简介

看到这里显然有一个疑问，树模型不是一直都用来分类的吗，怎么可以用来分割呢？答案是作者通过巧妙的方式把分类转换为了分割。我们称2D图像中的像素点叫做Pixel，那么3D图像中的像素体就叫做Voxel（体像素），由一堆Voxel组成的小立方体就是Patches（块像素）。

那么将40张CT图像分割成30000重叠的块像素，每个块像素提取1400个特征，训练NAFs进行分类，类别是块像素中占比多的那个内脏：

对于一幅新输入的待分割CT图像，我们也切分成重叠的块像素，提取同样的特征，遍历NAFs，每棵树都会找到很多30000训练patches中的“最近邻”patches，并且根据概率有一个相似度。我们只选择相似度最高的前20个最近邻patches。

对这20个最近邻Patches，创建一个搜索窗，用归一化积相关算法(NCC)进行相似度匹配，得分最高的Patches就会被选为候选Patches（candidate patches）。这样每一个voxel都会被若干候选Patches覆盖，他们的投票值最高的标签就作为这个Voxel的标签，这样一来就用Patches的分类完成了Voxel分割：

NAFs原理

整个分割过程大致有了了解，关键点有两个：如何构建随机森林去近似邻域？如何处理特征？

我们定义整个图像集为I，每张图像I∈I，一个图像子集为{Ip}p∈[1,P]，两幅图像之间的距离定义为ρ(·, ·)，具体数值为ρ(I, J)，J为新输入的图像。NAF就是寻找k个和J最相似的I∈I，也就是使得ρ(I, J)最小的k个I，定义这个最近邻图像集合为N_kρ(J)。可以想象直接搜索这个N_kρ(J) 是十分费时间的，而且如果采用“年龄”来定义距离，新图像是没有“年龄”这种属性的，所以距离根本不可测。NAF就是通过构建随机森林来近似这种邻域关系，相当于把这种距离保存在了树的结构里，只需要遍历森林测试特征就可以了，完全不需要去计算距离。

NAFs树的测试过程

NAF的树是二叉决策树，给定一幅图像J，它会依次遍历每棵树，从根节点s0开始一直找到叶节点，叶节点里保存着训练图像ID，如果新图像和那些叶节点都走了相似的路径，那说明它们本身也是相似的，这就是最近邻图像集合。我们把单棵树产生的最近邻图像集合定义为N_T(ρ)(J)，也就是新图像J按照ρ定义遍历第T棵树产生的Neighbours。论文的示意图很容易看懂，就是简单的决策树测试而已：

NAFs树的训练过程——特征降维

定义图像I的特征向量为f(I)∈R^Q，因为是图像，所以f非常可能是一个高维的特征向量，例如Q=10000。那么必须得降维，否则就当场去世了。随机森林的随机是一个又鲁棒又能降维的东西，我们先随机挑选特征f_T(I)∈R^q，q<Q，f_T(I)∈f(I)，这样既降低了维度，又使得每棵树更加独立。然后在每棵树训练期间节点分叉的时候，我们总是再次从f_T(I)中随机挑选M个特征进行遍历来做出二分抉择，M<=q，f_MT(I) ∈f_T(I)。两次降维已经够了。我们定义节点的图像集合为I_S，分叉后左节点图像集合为I_SL，右节点图像集合为I_SR，那么对于图像In∈I_S来说，分叉条件为：

f_mT(In)指的是In这个图像的第m个特征值。我们的目标就是优化参数m和τ，使得划分得最开，很明显要使用熵了。但这里的距离ρ不是传统的距离，可能是语义距离，所以这里的熵需要进行特殊定义。我们首先定义集合A的空间紧凑性为：

很容易理解，两两距离求和再平均，如果这个值越小，说明两两之间距离越小，那么就越紧凑（图像越相似），所以定义熵为：

根节点的紧凑性减去分叉后的紧凑性的加权，反映了按照当前m和τ划分子树根节点的紧凑程度，熵越大，划分也就越好，所以整个问题变成了求最优化解：

其中Δ是树的停止条件之一，也就是叶节点必须要有的最小图片数目。求解的过程就是对于每个m取值，我们遍历所有的τ划分点取值，求得使得熵G取到最大值的m和τ，虽然前面两次降维，但这个遍历过程仍然是一个很费时的操作。

训练树的停止条件：树的深度、最小样本数Δ、G<0。前两个就是决策树的基本停止条件，G<0意味着划分下去反而变得不紧凑了（图片之间相似程度更低了），所以还不如不要分直接停止生长。

NAFs的测试过程

对于给定的图像J，测试每棵树，找到叶节点最近邻图像集合N_T(ρ)(J)，我们给这些图像计数，那么得分最高的前k个显然是整个森林都认为很相似的最近邻图像了。定义1A(x)为sign函数，若x∈A则1A(x)=1，否则1A(x)=0，那么测试的计数得分用数学公式表示为：

也就是新图像J在距离ρ的定义下，森林F中各棵树T判断是否和训练图像In相似的求和值。

NAFs参数调整

NAF有很多参数：

（1）叶节点最小图像数目Δ
Δ越大，划分越粗糙，降低KNN精确度；Δ越小，越容易过拟合。

（2）最大树深
树深越小，划分越粗糙，降低KNN精确度；树深越大，对内存和算法性能要求就越高。

（3）树的数目
刚开始增加明显提升精确度；当树的数目达到一定程度后，精确度就不会有明显提升了。

（4）特征空间大小Q和降维q、M
q/Q越大，那么树的独立性越小，都训练出一样的树那还要森林有什么用呢。q/Q通常根据具体的Q值来确定，例如Q=10000，则q/Q取0.1，q=1000；Q=3000，则q/Q取1/3，q=1000。

M同理，可以根据机器性能和期望的邻域近似准确度去调整。

NAFs优势和劣势

从前面可以看出，整个分割过程其实就是一个寻找KNN的过程，不过NAFs的好处在于，它不需要进行配准（因为使用块像素的相似来进行分割的，而不是建立严格的数学模型），并且它可以用于“语义距离”。举个例子，我们要对脑部CT图像进行分类，判断这个人是多少岁，通常定义的距离都是这两幅图像的相似程度，比如欧式距离，而NAFs可以将“年龄”这个语义属性作为两幅图像的距离，也就是年龄差作为图像距离。这个和图像的像素值一点关系也没有，只和图像属性有关系。同时，因为构建了随机森林来保存这种块像素之间的近似相似性，所以搜索的速度非常快，不需要每个块像素去单独比对，只需要遍历NAFs即可。使用随机特征和树模型，能够很好地避免过拟合。

然而，如果Patches很多，那么整个训练过程会异常缓慢，并且需要巨量的内存和硬盘；并且这种方法只能适用于图像非常近似的分割（比如CT图像几乎变化不大），不能用于图像变化剧烈的，那种剧烈的还是老老实实使用神经网络吧。使用树模型，要调整的参数非常多。