球面图像的SLIC算法

吴 刚， 施云惠， 尹宝才

(北京工业大学信息学部， 北京 100124)

360°视频/图像，也称为全景视频/图像，是一种新型的多媒体图像. 不同于传统的仅涵盖有限二维(2D)平面的视频/图像，360°视频/图像是定义在球面域的图像，可以无缝地环绕观看者，为用户提供沉浸式的观察体验[1]. 它还是虚拟现实内容的基本载体，已随着虚拟现实技术飞速发展，渗透到人们的日常生活，并迅速地改变人们的日常生活方式. 面向球面图像处理的研究也引起了学术界和工业界的极大关注.

超像素分割将图像像素中相近的、具有类似属性的多个像素进行合并，组成具有一定意义的原子区域——超像素，从而代替原始的图像像素. 这些原子区域大多保留了进一步进行图像处理的有效信息，且一般不会破坏图像中物体的边界信息. 属于某超像素区域的像素共享相似的视觉属性，因此超像素分割可以提供一种方便和紧凑的图像表示. 超像素分割能大幅度降低实际问题的计算量，提高运算效率，被广泛地应用于图像分类[2]、识别[3]、三维重建[4]等领域，其分割效果一定程度上决定了后续应用的性能. 超像素分割方法众多，主要分为基于图和基于聚类的方法[5-6]. 其中，最常用且效果好的算法是简单线性迭代聚类算法(simple linear iterative clustering，SLIC)[7].

超像素分割算法通常是面向平面域图像设计的，无法直接用于处理球面域的图像. 通常，人们将球面图像投影为一幅或多幅平面图像，再利用平面图像处理算法对生成的平面图像进行处理. 然而，球面图像和平面图像是分别定义于流形和欧式空间的不同信号，从球面向平面的投影过程会产生新的边界，且容易导致球面数据采样的不均匀，从而破坏球面图像数据的局部相关性. 因此，球面图像的超像素分割算法并不能完全采用平面上的超像素分割方法. 为解决这一问题，一些研究工作通过重新定义等距柱状投影(equirectangular projection，ERP)图像像素间距离度量以适应球面数据的相关性，改进平面的超像素分割算法以适应球面图像[8-9]. 这些超分辨率算法引入了复杂的球面几何计算，仍然无法克服平面化带来的数据扭曲和破坏问题.

本文提出了一种球面图像的SLIC算法. 该算法在球面数据近似均匀分布约束下，对ERP图像表示的球面图像进行重采样，并将重采样数据重组，生成一个新型的球面图像的平面图像表示. 该球面图像表示既可以最大限度地保证球面图像数据采样的均匀性，也能保持图像数据的局部相关性. 在所提图像表示下，将球面的几何特性整合到经典的SLIC算法中，构建了球面图像的SLIC算法. 该算法与传统平面图像的SLIC算法相比，不仅能够提高球面图像超像素分割的客观质量，而且可以显著地提升球面图像超像素分割的主观效果.

1 球面图像重采样

1.1 球面三角层级剖分及采样点分布

球面图像通常以ERP图像的格式存储，但这种格式会带来形变和图像的局部相关性破坏. 同时，采样的不均衡会导致球面图像在某些区域(如极点区域)的大量冗余[10-11]，这严重地影响了SLIC算法的性能. 图像重采样是将给定连续图像的一种数字图像表示转化为另一种数字图像表达的过程[12]. 在这个过程中，通常会改变像元点的采样分布. 因此，本文需要利用重采样将输入的ERP球面数字图像重新采样为保持球面特性的数字图像，使得该表示利于后续的超像素分割处理.

为了建立均匀采样球面图像，首先选择合适的采样栅格模型以建立重采样后的球面像元. 球面近似均匀格网包括：三角形格网、菱形格网和六边形格网. 其中球面三角形格网是最基本的球面剖分格网，球面六边形格网和菱形格网都可以通过球面三角格网生成. 在天文、地理等学科领域众多的研究中，通常用三角格网逼近球面[13]. 为此，本文采用球面三角格网作为采样栅格，将球面图像的像素表示为三角形的像素. 为生成球面三角格网，需要对球面进行三角剖分，这里采用最简单的剖分方法——经纬度平分法. 该方法首先将球面平分为8个大小面积完全相等的球面三角形，然后采用递归方式以大圆弧连接每个球面三角形3条边的中心点. 每次连接可将原球面三角形剖分为4个更小的球面三角形，重复此操作直至相应的剖分层次n. 这种方法简单易实现，能够生成近似均匀分布的球面三角格网.

进一步可以将采样点位置定位于每个三角格网单元中的形心，最终得到一组在球面上近似均匀分布的球面三角像元. 其形心位置的计算以及与球面坐标之间相互转换的方法参考Goodchild等[14]的工作. 重采样后的球面三角像元数量为8×4n个.

图1(a)显示了生成球面三角格网的剖分过程. 通过投影坐标转换，找到球面三角像元点在ERP平面对应位置，最后利用普通平面图像插值方法，如双线性、双三次插值，即可获得对应的球面三角像元的值[15]. 图1(b) 显示了从一幅ERP图像重采样成球面三角图像的过程. 从该图像可以看出，重采样后的球面图像三角像元在球面上的分布位置由之前生成的球面三角格网模型给定.

图1 球面三角格网模型及球面三角像元生成过程Fig.1 Procedure for generating spherical triangle grid model and spherical triangular pixels

为进一步比较重采样的效果，本文对比了ERP图像与重采样后球面图像的像元点在球面上的分布密度. 在采样点数量同为131 072的情况下，图2以可视化的方式对比了球面图像在重采样操作前后的采样点分布情况. 图2(a)和图2(b)分别为ERP图像像素点和重采样后的球面三角像元点在球面上的分布情况. 图2表明重采样后生成图像的采样点分布更加均匀，重采样后的图像克服了ERP图像在两极区域采样的冗余，有效地保持球面图像数据的局部相关性.

图2 ERP图像与球面三角像元图像像素点球面分布密度对比Fig.2 Comparison of the pixel distribution density of the ERP and the spherical triangle image on the spherical surface

1.2 球面图像三角像元重排列

重采样得到的新的球面图像冗余度较小，邻域关系与球面三角格网关系一致. 然而，如上所述，SLIC算法是定义在平面上的算法，为适应SLIC算法，只处理欧氏几何，避免引入较复杂的球面几何，可以在保持球面三角像元原始邻接关系的基础上，对这些像元进行某种形式的二维排列.

本文给出了一种适合进行超像素分割的球面像元排列方式. 该方式能最大限度地保留球面图像像元间的拓扑关系，保持相关性. 该排列方式的像元扫描路径如图3所示.

图3 球面三角像元重排列扫描顺序Fig.3 Scanning order for the rearrangement of spherical triangle pixels

球面三角剖分后可以生成8个完全对称的球面三角形. 为排列成二维形式，需要规定像元的二维扫描顺序. 扫描时按从低纬度到高纬度的顺序，即从赤道分开，从中间朝上下2个方向进行扫描. 朝向不同的三角像元被依次分配至平面图像的不同行. 北半球从赤道开始到北极，依次排列朝上、朝下的三角像元；而南半球正好相反，从赤道向南极扫描的过程中，依次排列朝下、朝上的三角像元. 图3以平面三角的方式显示了其中4个大球面三角形经过2次剖分后的邻域排列及扫描过程，其余7个大三角区域的球面三角单元的排列方式与此完全相同.

以该扫描方式排列后，图像像元向二维平面的中心集中，形成类似菱形的形状. 图4给出球面三角像元重排列后二维图像各区域的尺寸参数. 所有像元集中在二维平面的菱形区域内，具体尺寸随行列变化. 可令重排列后图像的行和列索引分别由i和j表示，w表示重排列后图像的宽度，h表示该图像的高度，则有

图4 重排列球面三角像元后生成的二维平面图像尺寸参数Fig.4 Size parameters of the 2D images generated by rearranging spherical triangle pixels

(1)

令图像区域距离左边界的宽度为L，图像区域的宽度为M，图像区域距离右边界的宽度为R，它们相应的取值范围为

(2)

式中

j'=h2-j-1-2jh.

2 基于SLIC的球面图像超像素分割

图5显示了一幅球面图像经过采样和重排列后形成的二维表示. 在二维表示下，出现无效像素区域(绿色区域)，同时，平面化排列的球面图像有边界存在. 然而，球面图像只在边界处的连续性遭到破坏，球面三角像元间的相关性基本保持.

图5 球面三角像元重排列后生成的二维图像表示示例Fig.5 Example of a 2D image representation generated by the rearrangement of spherical triangle pixels

本文期望在平面的SLIC算法框架下，建立球面图像的SLIC算法. 为此，需要在区域初始化阶段考虑无效区域的影响和SLIC算法迭代过程中边界的特殊处理.

2.1 初始化及无效种子的去除

传统SLIC算法需要根据预先设定的参数，如要生成的超像素块数K以及每块的像素数来确定种子位置，该过程通常还包含必要的颜色空间转换、梯度修正等过程. 在已经将球面图像重采样并重排列后，SLIC框架可以被最大限度地保留. 初始化过程主要是进行颜色空间转换，以及确定超像素区域个数、种子点(seeds)的位置. 初始化过程中每个区域包含的像素个数为4n×8/K.

由于重采样后的图像具有无效区域，故需要对某些种子进行丢弃. 丢弃策略非常简单，主要就是依据式(1)(2)所给定的二维表示的有效区域范围，计算某种子的搜索邻域是否与有效区域有重合，对没有重合的种子直接丢弃，后续不再进行处理.

2.2 边界处理

球面图像定义在球面域，像元具有连续性和周期性. 重排列成二维平面图像会打破这种周期性，产生原本并没有的边界. 因此，需要对边界区域特殊处理，尽量保持边界像元间的连续性. 对于重排列图像，每行有效像素数量为w-⎣(j+1)/2」×4.

根据球面像元在球面上的原始相邻关系，重排列后的左右边界元素在球面上是沿纬线方向相邻. 据此可得出边界处理的策略，即碰到“超出”边界的像元，则沿纬线方向以类似周期拓展方式，从相反边界处找到对应的像元，从而实现边界“黏合”.

图6给出了“黏合”后图像的示意图，其中阴影区域代表对应的像元填补区域. 从图6上方S所处的球面位置可以很容易看出，平面上处于跨边界区域中的点P与P′实际上应该是同一个点，P点与左边界、P′与右边界之间沿某方向的横向距离应是相等的. 因此，在重排列后的二维图像中，从右边界与P处于同行的像元开始沿纬线方向进行周期性的延拓，即可得到与P所对应的点P′. 同理，当种子S处于右边界附近时，搜索区域中位于无效区域的点需要从左边界处沿纬线方向寻找. 从本质上来说，以上这种周期性的等长延拓，可以将平面化时被分开的边界重新“黏合”，还原球面数据的周期性和球面几何的封闭性，从而较好地保持球面数据的原始特性.

图6 边界“黏合”处理示意图Fig.6 “Adhesion” procedure for the borders

在SLIC算法框架下，完成距离计算及标签更新后，还需要更新种子的位置，作为下一次迭代种子点. 该更新过程同样需要对重排列图像的边界区域进行特殊处理，处理策略与搜索时处理方式类似. 需要判断当前种子离左边界近还是离右边界近，从而判断边界循环补齐位置. 即若距离左边界近，则将右侧边界处像元取出补全，对应图6左上方种子的情况；若距离右边界近，则取左侧像元补全，对应图6右下方种子的情况. 在边界区域内求出更新种子的坐标后，还要判断新种子是否位于有效区域内，若不在区域内，则将其移至有效区域内，最终完成种子位置的更新.

2.3 超像素边界可视化

在球面图像超像素分割算法完成后，需要将超像素分割的结果展示出来以判断分割的主观质量. 换言之，需要在球面图像上可视化每个超像素的边界. 平面图像超像素分割结果的可视化过程是非常简单的：首先判定四邻域或八邻域像元是否有不同的超像素区域标签，从而确定每个区域的边缘像素，然后对该边缘像素的四邻域或八邻域标注某种特定的颜色即可. 对普通图像的平面四边形格网模型来说，四邻域和八邻域的检索只是对图像的行和列索引进行简单的运算. 但是对球面图像的三角像元而言，其邻域与平面图像矩形像元截然不同. 为此，需要针对其特点给出可视化处理方法.

球面三角形像元的邻域可以是边邻域，也可以是角邻域. 图7展示了球面三角像元不同邻域层次的情况. 其中与中心球面三角像元模型单元有公共边的3个单元为边邻域(橙色)，共点的9个单元为角邻域(蓝色)，共有12个邻居[16]，且由角邻域向外生长，能生成更多的包含更多邻居的邻域，边界判定过程主要是判断检测某球面三角像元的邻域(三邻域或十二邻域)中是否具有不同的超像素区域标记. 具有不同标记的则可视该球面三角像元为边界像元，并对其着色，从而形成最终的可视化效果.

图7 球面三角像元邻域(十二邻域)Fig.7 Neighbors for a spherical triangle pixel (12 neighbors)

2.4 算法描述

本文所提算法的基本框架仍然基于平面SLIC算法. 但是为了适应经过重排列的球面三角像元，需要对SLIC算法进行改进. 根据之前的分析，针对重排列后的球面三角像元的排列方式，将无效种子的去除以及超像素边界的可视化整合到经典的SLIC算法中，建立一种球面图像的SLIC方案.

该算法针对经典SLIC算法的改进部分主要涉及：1) 去除重排列后的无效像元影响；2) 处理平面排列后产生的边界连续性破坏；3) 改进边界染色过程以适应球面三角像元邻域特点. 改进后的算法能够直接作用于重排列后的球面三角像元组成的二维图像上，直接输出分组标签数据和可视化结果. 其具体算法由算法1给出. 算法1是以重采样并重排列后生成的球面图像的二维表示作为处理对象，所以该算法的执行必须以重采样及重排列为基础. 从整体上来说，为生成最终的球面图像超像素分割结果，总共需要完成以下4个步骤.

1) 重采样生成球面三角像元. 根据第1节的球面三角格网剖分，生成球面三角像元采样点的球面坐标，然后将球面坐标以ERP投影方式转换为ERP图像平面上的平面坐标，再通过平面插值方法从ERP图像获取采样点的值. 本文采用双线性插值方法来具体实现该插值.

算法1 球面图像的SLIC算法

输入：重排列后球面图像I、超像素个数K、紧致性参数m、迭代次数t

输出：超像素标签集合{Sk}、可视化图像Is

① RGB颜色空间转LBA /*初始化*/

② 计算种子数量k及位置

③ 去掉不包含有效像元的种子

/*迭代开始*/

④ For每个有效种子区域Ck/*计算距离*/

For每个区域内像元xl

If边界区域像元 /*边界处理*/

边界处理

End If

计算距离dk

更新xl标签Sk

End For

End For

For每个区域Ck/*更新中心*/

If 边界区域 /*边界处理*/

补齐并更新中心

中心位置修正

Else

更新中心位置

End If

End For

⑤ 合并较小区域，更新标签{Sk}

⑥ 重复④和⑤t次

⑦ 三角像元边界染色 /*边界染色*/

2) 重新排列球面三角像元. 将第1)步中生成的球面三角像元重新组织成新的二维图像.

3) 执行算法1. 直接在重排列后的球面三角像元平面上执行球面图像的SLIC算法. 该算法去除了无效像素的影响，并将边界像元“黏合”起来，以保持球面像元在球面上周期连续的几何特性.

4) 可视化超像素边界. 为直接查看超像素分割的结果，需要以球面三角像元的十二邻域作为边界判断依据，完成超像素边界着色过程，形成可视化结果.

3 实验结果

为进一步验证本文所提算法的有效性，在JVET提供的360°视频测试集中提取某些帧作为测试图像[17]. 这些测试图像均以ERP格式存储，分辨率为4 K或8 K.

与不进行重采样的方法相比，该方法在重采样阶段就可以大大减少数据冗余，减少迭代过程中像素遍历的数量. 采样后的球面图像三角像元数量为4n×8个，调整剖分层次n的值可以控制超像素算法需要处理的像元总数. 在基本不影响视觉效果的情况下，分辨率为4 K的ERP图像可以取重采样的剖分层次n为9或8，则最终生成图像的大小只有原始图像1/4或1/16. 显而易见，在某些对像元颜色精度要求较低的应用中，该方法可有效降低数据量，提高运算效率.

为比较球面图像SLIC算法的有效性，在重采样后的二维图像和ERP图像上分别实施了平面SLIC方法以及球面图像SLIC算法. 图8对比了4组分别采用2种方法的可视化结果. 每组第1行是直接使用平面SLIC算法的结果，第2行是采用本文算法的结果. 图8(a)统一将所有超像素分割结果投影为ERP图像，以利于观察. 白线上部和下部分别为超像素数量1 000左右与200左右的分割结果. 图8(b)则展示了超像素分割结果在球面上的可视化效果. 可以明显看出，直接在ERP上执行超像素分割会在靠近两极位置产生明显的收缩，而本文方法则不存在收缩问题. 该实验表明直接在ERP上执行SLIC方法并不能很好地反映球面像元的几何特性，生成的超像素区域有明显的缺陷. 而本文方法可以有效保持数据的邻域特性，基本等同于直接在球面上进行像元距离计算，生成的超像素区域较为合理.

图8 在ERP上使用SLIC与本文方法生成的超像素分割结果对比Fig.8 Comparison of the visual results of the superpixel segmentations of the proposed method with those generated by applying SLIC to ERP images

除此之外，图9对球面上部分超像素区域的边界进行了展示. 图9(a)显示了直接在ERP图像上执行SLIC算法的超像素分割结果，图9(b)是本文方法的结果. 在对比图上可以看到，原始SLIC方法所生成的超像素区域边界产生了明显的断裂. 说明在ERP上直接使用平面图像的SLIC算法会生成边界无法闭合的超像素区域. 该问题主要是由于球面图像平面化后边界不连续所造成的，而本文方法将球面几何关系引入了球面SLIC算法，能够保持边界像元其在原始球面上的连续性，使得到的超像素边界轮廓闭合.

图9 不同方法产生的超像素边界闭合情况对比Fig.9 Comparison of the contour closure of the superpixels generated by different methods

为进一步判断本文超像素分割方法的效果，还给出了分割效果的定量对比. 由于目前还没有关于球面图像分割的基准标注数据，因此需要用不依赖于分割基准数据的度量方式. 本文采用可解释性变异度量(explained variation，EV)作为具体的度量方法[5，18]，其具体计算公式为

式中：SK为超像素分割后的一个超像素区域；μ(I)、μ(SK)分别为部球面图像像元颜色均值和超像素区域SK中所有像元颜色值的平均；I(xl)为像元xl的颜色值. 该度量方式不依赖人工边界标注，可以利用边界部分较大的颜色和结构变化，估算边界的附着性，值越大，代表效果越好. 图10对比了球面SLIC方案与平面SLIC方案的可解释变异度量值曲线. 图中K为超像素算法中的输入参数，表示要生成的超像素的初始数量. 从曲线来看，本文方法可以取得较大的EV值，超像素区域一致性较好.

图10 EV数值曲线对比Fig.10 Comparison of the EV curves

以上的实验表明，先对球面图像进行重采样和重排列，再在生成的二维图像上执行球面图像SLIC方法，所生成的超像素分割结果能够获得较好的主客观质量，比直接在ERP图像上执行SLIC算法更加符合球面特性. 本文方法实际上保持了原始球面图像数据间的相关性和邻域关系，解决了球面图像平面化过程带来的数据不连续和相关性破坏的问题.

4 结论

1) 通过重采样等过程生成的球面图像表示，可以较好地保持球面图像数据的局部相关性.

2) 本文算法能够正确处理球面数据的几何关系，所生成的超像素比SLIC算法更加合理，超像素分割性能与物体所在的球面图像的区域无关.

3) 本文算法所生成的超像素分割结果在客观质量上优于SLIC算法，超像素区域数据具有较好的一致性.

4) 本文算法所生成的超像素区域边界轮廓闭合，不会产生断裂的问题.