随着遥感影像空间分辨率的提高，面向对象的影像分析方法(object-based image analysis, OBIA)通过将离散的同质像素合并为具有实体意义的对象，扩展了影像特征表达能力(Blaschke等，2014)。影像分割中的尺度是指影像对象(对象细节)在空间跨度上的大小(明冬萍等，2016)。在面向对象的影像分析中，往往采用多尺度分割的方法获得影像在不同尺度上的表达，但是目前大部分多尺度分割算法存在尺度概念不清、尺度分割与尺度选择混淆以及算法适应性差等问题(胡忠文，2013)，很大程度上限制了其在遥感影像分析中的应用。

Guigues等人(2006)提出的尺度集模型是一种基于区域合并的影像多尺度分割模型，有效缓解了影像多尺度分割中存在的诸多问题。尺度集模型首先对影像进行初始过分割，并按照相异度由小到大的顺序不断两两合并邻接区域，直至合并为一个覆盖整幅影像的区域。尺度集模型利用二元分割树(Vilaplana等，2008)记录合并过程中产生的新区域以及所有子区域与父区域之间的层次关系，由此可以快速回溯至合并过程中的任意位置。作为一个底层框架模型，尺度集模型具有清晰的尺度概念，并且可以兼容不同的初始分割算法以及区域相异度评价准则。另外，尺度集模型还实现了将影像多尺度分割与尺度选择分离，通过二元分割树记录尺度集构建过程中产生的所有中间尺度，将尺度选择问题留给后续单独处理。在尺度集模型的模型优化和效率提升方面有众多研究，Hu等人(2016)提出了一种双层尺度集模型，在影像分块后，通过底层分块尺度集并行计算与顶层分块尺度集合并，实现了大幅面遥感影像上尺度集模型的快速构建；吴宁和陈秋晓(2012)将区域对象的属性、邻接关系和相关行为等进行了封装，并优化了尺度集等级队列的构建机制；张学良等人(2015)将尺度集模型分为图模型的构建、合并准则的确定、合并策略的选择、尺度参数的选择和分割树的设计共5个部分，并分别进行了优化设计。但以上研究都没有解决传统尺度集模型中底层数据结构复杂、构建效率低下以及冗余尺度较多的问题。

为此，本文提出利用全局区域相异度阈值驱动构建稀疏尺度集模型。该模型将尺度概念由合并区域总数转换到全局区域相异度阈值序列上，保留了传统尺度集模型尺度概念明确和适应性强等优点，同时简化了底层数据结构，提高了模型的构建效率，可以自由调整总尺度数。

图 1为稀疏尺度集的构建概念图，稀疏尺度集保留了传统尺度集生成有序尺度序列的基本思想，如图 1(a)，稀疏尺度集同样采用二元分割树记录区域合并关系，整个合并过程是从初始分割区域开始严格自底向上进行的。初始分割区域数为$N$且完整合并时，稀疏尺度集与传统尺度集的区域合并数均为$N$－1。

稀疏尺度集与传统尺度集存在以下不同：

1) 模型构建方式不同。传统尺度集的构建过程中，邻接区域严格按照相异度由小到大的顺序合并。稀疏尺度集则通过不断重复“扩大全局区域相异度阈值”与“合并所有相异度小于全局区域相异度阈值的邻接区域”2个步骤完成模型构建。

2) 生成的有序尺度序列密集程度不同。传统尺度集每发生一次区域合并就会在尺度序列中插入一个尺度单元，相邻尺度间无法插入中间尺度，因此是密集的。而稀疏尺度集相邻尺度间的区域合并数不固定，存在中间尺度。

3) 尺度定义不同。传统尺度集的尺度定义对应于发生区域合并的次数，而稀疏尺度集对应于全局区域相异度阈值扩大的次数。如图 1(b)中的稀疏尺度集，全局区域相异度阈值共扩大4次，包括初始分割结果在内共有5个尺度。

图 2为稀疏尺度集的构建流程，由于无法获得区域合并数与全局区域相异度阈值间的显式函数关系，因此本文通过重复进行预测和反推实际值2个步骤依次获得各个尺度的全局区域相异度阈值，同时加入了合并终止策略解决预测滞后问题。稀疏尺度集中初始分割与区域相异度评价准则采用与传统尺度集相同的框架，可以兼容多种不同的初始分割算法与区域相异度评价准则。本文采用SLIC(simple linear iterative clustering)超像素分割算法(Achanta等，2012)作为初始分割算法，采用Baatz和Schäpe(2000)提出的基于区域光谱和空间异质性加权和的区域相异度评价准则。

采用一个只记录邻接关系的区域邻接图(region adjacency graph, RAG)作为稀疏尺度集的底层数据结构，采用深度优先搜索获得满足合并条件的邻接区域。为了提高搜索效率，在搜索过程中记录各个区域的当前最小邻接区域相异度。在搜索到小于全局区域相异度阈值的邻接区域对$({\mathit{\boldsymbol{X}}}, {\mathit{\boldsymbol{Y}}})$后，通过以下3个步骤对RAG进行更新：

1) 合并满足条件的邻接区域对$({\mathit{\boldsymbol{X}}}, {\mathit{\boldsymbol{Y}}})$，初始化合并生成的新区域${\mathit{\boldsymbol{Z}}}$的区域属性信息与邻接信息。

2) 在RAG中删除区域${\mathit{\boldsymbol{X}}}$、${\mathit{\boldsymbol{Y}}}$和其所有邻接边。

3) 将${\mathit{\boldsymbol{Z}}}$插入到RAG中，更新所有与${\mathit{\boldsymbol{Z}}}$相邻区域的邻接关系。

采用邻接表保存RAG，由于严格遵循区域两两合并的准则，对于初始区域数为$N$的RAG，整个合并过程中生成的新区域数至多为$N－1$，因此邻接表的大小不会超过$2×N－1$。初始化${\mathit{\boldsymbol{Z}}}$的邻接信息需要对${\mathit{\boldsymbol{X}}}$、${\mathit{\boldsymbol{Y}}}$的邻接区域取并集，本文给定每个区域一个下标，在邻接表中初始化RAG的时候，对每个区域的邻接区域均按照下标从小到大进行排序，并在后续RAG的更新中始终维护该顺序关系，使得取并集的时间复杂度由O$(N^{2})$下降为O$(N $ log$N)$。

稀疏尺度集放弃了传统尺度集构建中的最优合并准则，而是采用全局区域相异度阈值驱动区域合并。因此，全局区域相异度阈值序列是稀疏尺度集构建的核心。理想的全局区域相异度阈值序列应生成用户指定的总尺度数，同时使相邻尺度间的区域合并数相等。

通过调节稀疏度参数$d$，可以生成用户指定的总尺度数, 即

$ d = \frac{m}{{N - 1}} $

(1)

式中，$N$为影像的初始分割区域数；$m$为相邻尺度间的期望区域合并数。

则稀疏尺度集的理论总尺度数$K$定义为

$ K = \left| {\frac{1}{d}} \right| + 2 $

(2)

由于全局相异度阈值与合并区域数之间不存在显式函数关系，且当相邻尺度间区域合并数相等时，全局相异度阈值呈指数增长。因此本文采用三次指数平滑预测法(李颖，2009)依次计算各个尺度的全局相异度阈值。

尺度$k+1$的全局区域相异度阈值预测值$\widehat{C}_{k+1}$计算为

$ {\hat C_{k + 1}} = {a_k} + {b_k} + {c_k} $

(3)

$ \left\{ {\begin{array}{*{20}{l}} {{a_k} = 3S_k^{(1)} - 3S_k^{(2)} + S_k^{(3)}}\\ {{b_k} = \frac{\alpha }{{2{{(1 - \alpha )}^2}}}[(6 - 5\alpha )S_k^{(1)} - }\\ {{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} 2 \times (5 - 4\alpha )S_k^{(2)} + (4 - 3\alpha )S_k^{(3)}]}\\ {{c_k} = \frac{{{\alpha ^2}}}{{2{{(1 - \alpha )}^2}}}[S_k^{(1)} - 2S_k^{(2)} + S_k^{(3)}]} \end{array}} \right. $

(4)

式中，$S^{(i)}_{k}$是尺度$k$的全局区域相异度阈值$i$次平滑值；$α$是加权系数，由于全局区域相异度阈值序列变动幅度较大，取值一般在0.6~0.8之间。各个$S^{(i)}_{k}$计算为

$ \left\{ {\begin{array}{*{20}{l}} {S_k^{(1)} = \alpha {C_k} + (1 - \alpha )S_{k - 1}^{(1)}}\\ {S_k^{(2)} = \alpha S_k^{(1)} + (1 - \alpha )S_{k - 1}^{(2)}}\\ {S_k^{(3)} = \alpha S_k^{(2)} + (1 - \alpha )S_{k - 1}^{(3)}} \end{array}} \right. $

(5)

式中，$C_{k}$是尺度$k$的全局区域相异度阈值实际值。由于全局区域相异度阈值与合并区域数不存在显式函数关系，$C_{k}$是通过反推式(6)获得全局区域相异度阈值近似值，在算法中作为全局区域相异度阈值实际值使用，即

$ {C_k} = {\mathop C\limits^ \wedge _k} + \beta \frac{{{{\hat n}_k} - {n_k}}}{m}({\mathop C\limits^ \wedge _k} - {C_{k - 1}}) $

(6)

式中，$n_{k}$为尺度$k$的区域数实际值；${\hat n_k}$为尺度$k$的区域数预测值；$\widehat{C}_{k}$为尺度$k$的全局相异度阈值预测值；$β$为调节系数，取值一般在1~1.2之间。式(6)本质上是利用$C_{k}$与$n_{k}$相关性，将$\hat n_{\rm k}$与$n_{k}$的偏差映射到$\widehat{C}_{k}$与$C_{k}$上。由于$C_{k}$与$n_{k}$具有强相关性，且$C_{k}$的近似误差会在下一尺度获得自修正，大量实验已证明式(6)获得的$C_{k}$符合精度要求。

解决以上问题后，获取全局相异度阈值序列的完整流程如下。通过迭代计算的方式获得前3个尺度的全局区域相异度阈值实际值$C^*_{1}$、$C^*_{2}$和$C^*_{3}$($C^*_{1}$为0)，在基于$C^*_{1}$、$C^*_{2}$和$C^*_{3}$完成前3个尺度的区域合并后，设置加权系数$α$并取平滑系数初始值$S_0^{(1)} = S_0^{(2)} = S_0^{(3)} = \frac{{C_1^* + C_2^* + C_3^*}}{3}$。从$k=4$开始按照以下4个步骤获得各个尺度的全局区域相异度阈值并完成区域合并：

1) 通过式(3)获得尺度$k$的全局区域相异度阈值预测值$\widehat{C}_{k}$。

2) 以$\widehat{C}_{k}$为相异度阈值上限进行区域合并。

3) 通过式(6)获得尺度$k$的全局区域相异度阈值实际值$C_{k}$。

4) 尺度扩大1。

图 3为全局区域相异度阈值序列构建示例。中小尺度下，反推实际值与预测值偏差极小。从虚线对应的尺度开始，出现了明显的预测滞后现象，表现为预测值明显小于反推实际值，差值随尺度增大而增大。该问题主要由三次指数平滑预测法本身的性质，以及大尺度下相异度较大的邻接区域被强行合并造成。预测滞后问题会导致大尺度条件下，相邻尺度间区域合并数不稳定。本文在1.3节介绍合并终止判断的方法，在提升尺度集构建效率的同时规避预测滞后问题。

在稀疏尺度集的构建过程中，随着分割尺度的不断增大，影像分割状态由过分割逐渐过渡到欠分割。在区域合并进入欠分割状态时终止合并进行，可以去除实际价值不大的欠分割尺度(于欢等，2010)，进一步提高稀疏尺度集的效率，并解决1.2节中的预测滞后问题。影像分割质量与全局对象内部同质性、全局对象间异质性具有密切关系，采用局部方差(local variance, LV)(Johnson和Xie，2011)和莫兰指数(Moran’s index, MI)(Moran，1950)分别表示全局区域内部同质性和全局区域间异质性。影像分割尺度$k$的局部方差$L(k)$和莫兰指数$M(k)$计算为

$ L(k) = \frac{1}{{W \times H}}\sum\limits_{i = 1}^n {{a_i}} {\sigma _i} $

(7)

$ M(k) = \frac{{n\sum\limits_{i = 1}^n {\sum\limits_{j = 1}^{n,j \ne i} {{w_{i,j}}} } ({x_i} - \bar x)({x_j} - \bar x)}}{{(\sum\limits_{i = 1}^n {\sum\limits_{j = 1}^n {{w_{i,j}}} } )\sum\limits_{i = 1}^n {{{({x_i} - \bar x)}^2}} }} $

(8)

式中，$n$为当前尺度的区域总数，$W$和$H$分别为影像的宽度与高度，$a_{i}$和$σ_{i}$分别为区域$i$的面积和光谱标准差; $w_{i, j}$表示区域$i$和区域$j$的空间权重，若区域$i$与区域$j$邻接，则$w_{i, j}=1$，否则$w_{i, j}=0$。$x_{i}$表示区域$i$的色彩均值，$\bar x$表示整幅影像的色彩均值。$L(k)$越小，表示该尺度下全局区域内部同质性越高；$M(k)$越小，表示该尺度下全局区域间的异质性越高。

在此基础上，利用改进的尺度集简化框架(Hu等，2017)，对MI进行单调化处理以满足归一化后单调递减的需求，处理为

$ \begin{array}{*{20}{l}} {M(k) = {\rm{min}}\{ M(k),M(k - 1)\} }\\ {k = 1, \cdots ,N - 1} \end{array} $

(9)

随后将归一化的LV和MI转化为过分割和欠分割的风险，并引入惩罚因子$Q$惩罚过分割，使得当风险函数最小时影像分割处于欠分割状态，并在此时停止区域合并的进行。影像分割尺度$k$的风险函数$r(k)$计算为

$ r(k) = Q\sum\limits_{i = 1}^k {{P_{\rm{U}}}} (i) + \sum\limits_{i = k + 1}^N {{P_{\rm{O}}}} (i) $

(10)

式中，$P_{\rm U}(i)$和$P_{\rm O}(i)$分别为$L(i)$和$M(i)$的归一化值，即

$ {{P_{\rm{U}}}(i) = \frac{{L(i) - {L_{{\rm{min}}}}}}{{{L_{{\rm{max}}}} - {L_{{\rm{min}}}}}}} $

(11)

$ {{P_{\rm{O}}}(i) = \frac{{M(i) - {M_{{\rm{min}}}}}}{{{M_{{\rm{max}}}} - {M_{{\rm{min}}}}}}} $

(12)

在合并开始时，通过影像初始分割可以计算获得$L_{\rm min}$和$M_{\rm max}$，通过原始影像(等价于合并至只剩一个区域)计算获得$L_{\rm max}$，$M_{\rm min}$取经验值-0.03，并在合并过程中将小于$M_{\rm min}$的MI取值修改为$M_{\rm min}$，由此实现了在区域合并的过程中计算$P_{\rm U}$和$P_{\rm O}$。图 4为区域合并过程中$QP_{\rm U}$、$P_{\rm O}$、$r$的变化趋势，当$QP_{\rm U}=P_{\rm O}$时风险函数$r$取得最小值，但由于稀疏尺度集的尺度是离散的，很难存在恰好满足$QP_{\rm U}=P_{\rm O}$的尺度，因此本文以合并过程中第1个满足$QP_{\rm U}(k)>P_{\rm O}(k)$的尺度作为终止合并尺度。

稀疏尺度集中所有需要设置的参数符号含义见表 1，其中$α$、$β$的默认经验值分别为0.8与1.05。实验电脑配置为Intel(R) Core(TM) i7-8750H CPU @2.2 GHz 2.21 GHz、32 GB RAM和500 GB SSD，操作系统为Windows10 64位。为了更好地评估稀疏尺度集在高空间分辨率影像中的分割准确度，实验影像采用0.1 m高空间分辨率无人机影像，影像大小为1 214×1 140像素。

传统尺度集区域合并遵循最优合并准则，本文将传统尺度集合并过程中的LV和MI作为标准值，将不同稀疏程度的稀疏尺度集在对应合并位置的LV和MI与标准值进行对比，以此反映稀疏尺度集相较传统尺度集的合并质量差异。实验中$N$取值3 000，为了获得完整的稀疏尺度集，本实验没有加入合并终止判断。为了便于理解，实验中已按照式(1)将抽象的稀疏度$d$转化为相邻尺度间区域合并数$m$。

如图 5，连续曲线为基于最优合并的传统尺度集(等价于稀疏尺度集$m=1$)合并过程中的LV与MI值。不同$m$取值的稀疏尺度集LV和MI几乎均落在标准曲线上。表 2利用均方根误差(root mean square error, RMSE)进一步精确量化了稀疏尺度集LV和MI相对于传统尺度集的误差，其中均方根误差$R_{\rm LV}$和$R_{\rm MI}$的最大值分别仅有0.102和0.434。实验中$m$的最大取值达900，对应稀疏尺度集只有5个尺度，可以认为实验稀疏尺度集区域内部同质性、区域间异质性与传统尺度集无明显区别。

图 6为分别采用传统尺度集与不同稀疏程度的稀疏尺度集，实验影像在区域数剩余1 200时的合并结果。从传统尺度集($m=1$)到最大稀疏度($m$=900)的稀疏尺度集，均没有发生区域错误合并，差异在地物内部过分割区域的合并顺序上。过分割生成的地物内部区域相异度往往极小，传统尺度集由于遵循最优合并准则，会严格按照相异度由小到大的顺序合并地物内部区域。实际上，地物内部过分割区域的合并顺序不是最重要的，只要区域合并完整，不发生错误合并即可。稀疏尺度集放宽了地物内部区域合并顺序的限制，获得模型构建效率的大幅提升。在达到欠分割尺度前，稀疏尺度集与传统尺度集的合并质量几乎相同。

合并终止机制的引入一方面可以清除冗余的欠分割尺度，另一方面可以规避大尺度出现的预测滞后问题。通过引入惩罚因子$Q$控制合并终止的尺度，图 7展示实验影像不同$Q$取值引起$P_{\rm U}$ 曲线和合并终止尺度的变化。当$Q$的值从1减小到0.4时，合并终止尺度从47逐渐增大到57，因此通过$Q$可以有效控制合并终止的尺度，$Q$的取值越小，合并终止尺度越大。

$Q$取值过大会使合并终止的尺度太小，导致合并终止在过分割状态的几率较大，损失有意义的尺度；$Q$取值过小会使合并终止尺度太大，形成大量的冗余欠分割尺度，降低模型的运行效率，放大预测滞后问题。

实验影像$Q=1$和$Q=0.4$合并终止时的合并结果如图 8所示，对应的尺度分别为47和57。其中，$Q=1$时终止尺度处于过分割向欠分割的过渡阶段，损失了之后有价值的尺度；$Q=0.4$时终止尺度处于非常明显的过分割阶段，产生了冗余尺度，并且已经进入到预测滞后的尺度中。由于最有价值的尺度(最优尺度)往往处于过分割向欠分割的过渡阶段，因此$Q$取值过大造成的后果远大于$Q$取值过小，实际中一般取经验值$Q=0.6$，此时合并终止尺度大概率为欠分割向过分割的过渡态。

不同参数取值会在很大程度上影响稀疏尺度集的构建速度，尤其是稀疏度$d$和初始区域数$N$。本文首先研究了稀疏度$d$对稀疏尺度集构建速度的影响，随后比较了不同初始区域数$N$下稀疏尺度集与传统尺度集的构建速度。默认参数按照表 1设置，$Q$均取值0.6。

表 3为实验影像在$N=3 000$时，不同稀疏度$d$对应的稀疏尺度集构建用时。构建用时分为区域合并和尺度属性计算两个部分，其中区域合并包括在RAG中检索满足小于全局区域相异度阈值的边和更新RAG；尺度属性计算包括计算当前尺度下的LV和MI、预测下一尺度的全局区域相异度阈值。随着$d$增大，区域合并的时间和尺度属性计算的时间均有所下降。$d$的取值对稀疏尺度集的构建时间有很大影响：$d=0.017$时，尺度间合并区域数为50，理论总尺度数为61，总构建时间达到22.082 s；$d=0.2$时，尺度间合并数为600，理论总尺度数为6，总构建时间仅6.414 s。

较小的$d$会使相邻尺度的全局区域相异度阈值差变小，加大在RAG中检索到满足条件邻接区域的难度。稀疏尺度集的区域合并时间存在理论上的上限和下限：当相邻尺度间只发生一次区域合并时($m$=1)，稀疏尺度集在合并效果上等效于传统尺度集，但是由于没有记录邻接区域相异度的顺序表，构建速度会远慢于传统最优合并尺度集，达到最慢的区域合并速度；当稀疏尺度集不存在中间尺度($m=N－1$)，即所有区域自由合并时，区域合并时间最少。尺度属性计算的时间消耗只与影像本身有关，实验影像中计算每个尺度LV和MI的时间消耗约为0.2 s，较小的$d$有更多的中间尺度，会导致尺度属性计算时间消耗的积累。

实验影像在$d=0.033$条件下，不同初始区域数$N$对应的稀疏尺度集构建用时见表 4，其中$m=100$，理论完整总尺度数为30。当$N$从500增大到3 000时，稀疏尺度集区域合并的时间从0.318 s迅速增长到9.207 s，尺度属性计算的时间基本不变，RAG边数从2 646增长到17 210。当相邻尺度间合并区域数不变时，总边数的增多加大了在RAG中检索符合条件的邻接区域的难度，区域合并时间迅速增加。由于总尺度数不变，因此尺度属性计算的时间基本不变。与传统尺度集的构建时间对比：总时间上，$N$取值不同的稀疏尺度集构建速度平均为传统尺度集的3.11倍。由于稀疏尺度集构建总时间中存在基本不变的尺度属性计算时间，当$N$较小时，稀疏尺度集的区域合并速度优势较大。随着$N$增大，稀疏尺度集构建速度优势会逐渐缩小，当$N$足够大时会被传统尺度集反超。但是$N$=3 000时实验影像的初始分割已经为充分的过分割状态，且实验中$d$的取值相对保守，因此一般影像分割任务中稀疏尺度集能够明显取得更高的效率。

本文提出了一种利用全局区域相异度阈值驱动构建的稀疏尺度集模型，阐述了模型构建原理，研究了核心参数对区域合并质量、合并中止判断和模型构建速度3个方面的影响，并与传统最优合并尺度集在区域合并质量和模型构建速度上进行了对比：

1) 区域合并质量方面。进入欠分割状态前，稀疏尺度集的区域内部同质性和区域间异质性与传统最优合并尺度集无明显区别，扩大稀疏度引起的是地物内部过分割区域合并顺序的变化。

2) 合并中止判断方面。通过调节惩罚因子$Q$可以消除冗余的过分割尺度，且可以规避大尺度下预测滞后问题。

3) 模型构建速度方面。扩大稀疏度$d$，可以通过降低邻接区域检索难度减少区域合并用时，通过减少尺度属性计算次数减少尺度属性计算用时。保守参数设置下的稀疏尺度集平均构建速度达到传统尺度集的3.11倍。

相比传统尺度集模型，本文提出的稀疏尺度集模型能够在不引起合并质量下降的前提下大幅度提高模型构建速度，并且可以通过调节参数适应各种不同任务需求。

稀疏尺度集模型也存在一些不足：

1) 通过三次指数平滑预测法获得的全局区域相异度阈值并不能精确控制尺度间的区域合并数，并且为解决大尺度下的预测滞后现象引入的合并中止判断降低了模型的构建效率。

2) 过大的初始分割区域数$N$会降低稀疏尺度集的构建速度，因此不适合处理超大幅面影像。

未来工作将进一步扩展稀疏尺度集的应用场景，探索合并区域数与全局区域相异度阈值间的深层次关系，寻找效率更高的邻接区域检索策略。