点击上方
“
小白学视觉
”，选择加"
星标
"或“
置顶
”
重磅干货，第一时间送达
A Fast Alpha-Tree Algorithm for Extreme Dynamic Range Pixel Dissimilarities
题目：一种针对极端动态范围像素差异的快速Alpha-Tree算法
作者：Jiwoo Ryu; Scott C. Trager; Michael H. F. Wilkinson
摘要
α树算法是一种有用的分层表示技术，有助于理解如遥感图像和医学图像等图像。大多数α树算法使用优先队列按正确顺序处理图像边缘，但由于传统优先队列在使用极动态范围像素差异性时效率低下，它们比其他相关算法（如组件树）运行得更慢。本文提出了一种新的分层堆优先队列算法，它可以比其他最先进的优先队列更有效地处理α树边缘。使用48位Sentinel-2 A遥感图像和随机生成的图像的实验结果表明，通过用所提出的队列替换堆优先队列，所提出的分层堆优先队列改进了洪水α树算法的时间：在Sentinel-2 A图像上分别为4-N的1.68倍和8-N的2.41倍，在随机生成的图像上分别为2.56倍和4.43倍。
关键词
I. 引言
理解图像需要基于大小、亮度和不同频率等特征识别区域和对象。分层图像表示通过从细到粗的尺度对图像进行分割，提供了一种有效的方式来实现这一目标[1], [2], [3], [4], [5]。许多这些应用使用树数据结构来构建分层表示，因为树数据结构提供了一种自然而有效的方式来表示不同尺度的图像分区层次结构[6], [7], [8], [9]。
α树用于诸如建筑区检测、图像/视频分割、人体解剖学图像分割、交通标志识别或植物疾病识别等应用[6], [7], [9], [10]。使用α树进行分割、检测或分类可以通过使用手工编码规则[6]或机器学习[10]来过滤α树节点来完成。深度神经网络（DNN）可以像在基于超像素的DNN算法中一样在α树节点上进行训练[11], [12]，尽管我们不知道有关此主题的任何已发布工作。α树算法通过合并具有均匀灰度级别或颜色的区域，即平坦区域来划分图像。平坦区域是连接分量（CC），其中其中的相邻像素具有低差异性。像素差异度量的选取取决于应用和计算复杂性。先前的研究在灰度或RGB颜色空间中使用了L2或L∞范数[6], [7], [9]。也可以使用其他颜色空间，如HSV、CIELAB，或使用高光谱图像[13], [14]，所有这些都会导致差异度量中的极端动态范围。
图1显示了从细（左）到粗（右）尺度的α树尺度空间，使用(a) RGB颜色空间中的L∞范数，(b) RGB中的L2，(c) CIELAB中的L2，和(d) HSV中的L2。CIELAB中的L
、a
和b*以及HSV中的H、S和V在计算L2范数之前都进行了归一化。请注意，H中的差异性以循环方式计算，需要对L2范数进行小的修改。在CIELAB或HSV的粗尺度中更好地保留了显着对象，如红玫瑰和白色真菌叶斑，使得它们的识别更加容易。使用L2范数而不是L∞的更高动态范围差异性也提供了更多的信息在结果α树中。图1(b)、(c)和(d)中的四幅图像是从数百万尺度中采样的，它们在实践中是连续的尺度空间，而图1(a)中的四幅图像是在这个范围内仅有的几百个尺度的尺度空间中的图像。Silla比较了RGB、CIELAB和HSV颜色空间在植物疾病检测的α树应用中，并发现使用HSV颜色空间中的L2范数提供了最佳的分割[10]。
使用更高动态范围像素差异度量显著提高了α树的性能，但它带来了高计算成本。当处理彩色或多通道图像时，像素差异度量的动态范围往往会变得非常高。即使彩色图像的每个通道在低动态范围（LDR）或高动态范围（HDR）中，其像素差异度量往往在极端动态范围（XDR）中，除非使用L∞范数或将差异性值量化。在LDR中的灰度图像中也可能有XDR的像素差异度量。Zhang和Wilkinson[15]引入了一个2-D Gabor滤波器，以沿着边缘强度的方向平滑边缘，以减少链式效应，从而产生更高动态范围的像素差异度量。然而，α树算法自[6]以来没有取得太大进展，据我们所知，还没有关于在XDR图像上工作的α树算法的已发布研究。在[6]中，提出了一种基于Berger联合查找算法的算法，它仅适用于LDR或HDR像素差异度量，因为使用了分层队列。在[17]中，提出了一种基于联合查找算法的并行α树算法，它也仅适用于LDR或HDR，因为随着位深度的增加，子图像块的子树合并的计算成本呈指数增长。在[18]中，提出了一种使用Kruskal算法构建α树的应用，它本质上是一种类似于联合查找的算法，它使用按排名联合和路径压缩来保持树的深度低。在[19]中引入了一种使用基于同调的工具的新方法，它提出了一种并行算法来在8位图像中构建α树。我们之前关于α树算法的工作使用了洪水算法和分层队列用于LDR图像，其中α树的大小预先估计以节省α树的内存占用[20]。
洪水（即基于合并的算法）是另一种类型的α树算法，基于最大树构造的原始洪水算法[21]。而联合查找算法通过按像素差异度量递增的顺序合并相邻的CC来构建α树，洪水算法通过在移动到另一个CC之前，在某个水平上“淹没”某个区域的某个区域来构建CC。而联合查找算法按递增顺序处理边缘但以看似任意的位置构建CC，洪水算法新创建的CC总是与已经构建的CC相邻，但不保证按递增顺序处理边缘。
冗余边缘（REs）是开发高效α树算法的最大挑战。RE是创建α树中冗余和残留节点的图像边缘，这些节点与其子节点携带相同的信息[6], [17]。它们因为大约75%的边缘在α树构造中是冗余的，所以在大多数α树算法中引起了主要的计算瓶颈[6]。由于RE，大多数使用联合查找或类似方法的传统α树算法在计算成本上遭受了重大的惩罚，因为检测和移除RE需要调用FINDROOT，据我们所知，这是O(log|E|)。通过使用洪水算法和分层队列，可以显著缓解这些边缘引起的减速，因为分层队列操作的计算成本都是O(1)[21]。然而，由于分层队列中的队列数量等于图像的动态范围，因此在HDR和XDR中分层队列变得完全不可行，因为它需要数百万甚至数十亿个队列，并且每个删除操作都需要对这些队列进行线性扫描。因此，当前最先进的算法在XDR中遭受显著的效率低下，如果使用更高的像素连通性，这个问题会变得更糟。例如，在8像素连通性中，边缘的数量是4像素连通性的两倍，因此冗余边缘的数量增加了三倍。
为了提高XDR中α树算法的处理速度，更好的优先队列设计是关键，因为在第三部分中显示，优先排队是XDR中α树算法计时的主要瓶颈。优先队列设计是离散事件仿真（DES）中待处理事件集（PES）中的一个研究充分的主题[22], [23], [24], [25], [26]。梯度队列（LQ）是PES中表现最佳的优先队列之一，它通过使用一个动态设置范围的队列层次结构，并且仅在需要时进行排序，从而具有O(1)入队（推送）和O(1)摊销出队（弹出）计算复杂度[25], [26]。LQ的结构由顶部、中间和底部梯度组成，其中顶部和中间梯度以未排序数组的形式存储项目，底部梯度在整个队列中存储唯一的排序数组。LQ与本文提出的分层堆队列（HHQ）在结构和目标应用方面有一些相似之处，例如分层结构和仅在必要时对项目进行排序。然而，LQ和HHQ在结构和目标应用方面有一些显著差异。LQ设计并不是为了存储大量的项目；[25]和[26]设置的最大梯度数量从2到5，这可以存储多达几万个项目。梯度数量少不仅适用于处理PES，其中预期入队和出队的数量是可比的，而且对于降低计算成本也是必要的，因为在LQ中入队一个项目需要将项目的时间戳与每个梯度进行比较。这与α树算法中的优先队列非常不同，其中在优先队列中可以存储高达数百万甚至数十亿条边。LQ的设计目的是适应具有变化概率分布的数据集，这在α树算法中并不必要，因为在α树算法中，大多数差异度量的分布具有指数或类似的右偏分布。即使差异度量分布的假设是错误的，通过在构建α树之前检查图像，很容易预先确定最优的层结构。然而，我们通过实证发现，假设指数分布始终优于在HHQ中使用最佳拟合估计。
在本研究中，我们通过提出一种新颖的HHQ算法来改进α树算法，该算法可以非常有效地处理RE。所提出的HHQ使用仅在需要时排序的队列层次结构。我们还提出了优先队列缓存，它不仅以非常低成本处理高优先级边缘，而且还通过大幅降低其级别检查成本，允许HHQ具有大量的级别。实证复杂性分析表明，HHQ的push和pop操作都是O(1)摊销的。使用所提出的HHQ、分层队列[21]、堆队列[27]和字典队列[28]进行的比较测试表明，HHQ通过减少RE的计算成本，在XDR中显著提高了α树算法的时间。本文的组织如下：第二节介绍了一种新颖的分层堆优先队列和使用HHQ的洪水α树算法，第三节显示了所提出的和其他α树算法的运行时间、分析和分析结果。
II. 方法
A. 定义
我们在此简要总结α树和相关术语的定义。我们按照以下方式定义与图像相关的术语：
我们将图像中的边权重
称为边 e 的“α值”。在许多α树洪水算法中，
也可以直接解释为边 e 的级别，它在洪水算法中充当循环控制变量：这里我们根据上下文交替使用这些术语。由于本文仅处理单通道图像，像素连通性只能是4邻接（4-N）或8邻接（8-N）。
图像 G 的 α 树是树形数据结构，其中节点对应于图像中的一组连接像素（即 CC）。α树的内部节点是通过创建叶节点和/或其他内部节点的并集形成的，它们通过边相互连接。由于最小生成二叉树只有
个节点，而边的数量是
，总有一些边是多余的，这些边在 α 树的构建中没有被使用 [6]。我们按照以下类型对 α 树边进行分类：
-
冗余边（RE）: 连接已经在较低级别被其他边连接的节点的边 [6]。
-
-
图 2 展示了从 2×3 图像构建的 α 树，包括 RE 和残余边。图 2(a) 和 (b) 分别显示了一个带有像素值和边权重（即 α 值）的 2×3 图像，以及图像的图 G = (V, E, w) 表示。图 2(c) 展示了从图 2(b) 中的图中构建的 α 树，其中有一条 RE e0 和一条残余边 e4。一个子树的根节点，如果其所有节点的 α 值低于或等于 αr，则称为 αr 级别的根。图 2(c) 中的节点 e6 和节点 e5 分别是在级别 5 和 2 的根。
B. α树算法中的优先队列
优先队列是任何 α 树洪水算法的重要组成部分。它们用于按边权重的升序对图像边进行排队，并且有多种数据结构，包括分层队列、堆队列和字典队列 [21] [27] [28]。分层队列在处理 LDR 和 HDR 像素差异度的 α 树洪水算法中工作得非常好 [20]，但对于 XDR，传统的优先队列是 α 树洪水的一个低效解决方案。这是因为，正如我们在本节中所示，α 树洪水算法中大约 85-90% 的图像边处理得非常低效，这可以从我们优化的排队策略中受益。
为了研究优先排队在 α 树洪水算法中的工作方式，我们在一张随机生成的图像上运行了洪水算法，并记录了每个边的以下信息：
-
队列时间：一个项目在队列中等待时从优先队列中删除的项目数量。
-
: 边 e 在队列中的位置
的最大值。例如，当 e 在队列中具有最高优先级时
。
-
这里边或项目的排名
是当所有边在 E 中按升序排列时它在层次结构中的位置。除此之外，我们还获得了非冗余、冗余和残余边的直方图。
图 3 显示了从单通道 64 位随机生成的 500 × 500 图像构建的 α 树中获得的优先队列统计信息。高优先级边（即权重排名接近零的边）在两种连通性下都具有非常短的队列时间和非常低的
。我们在图 3 的所有面板中都设置了一个任意阈值
，在
高于 12 的点，这对应于 4-N 中的 0.45|E| 和 8-N 中的 0.25|E|。图 3(b) 和 (d) 中的直方图显示，大多数这些高优先级边是非冗余的，这意味着它们是对应于 α 树中内部节点的大多数边。这解释了为什么 4-N 中的
更高，因为在 4-N 中，最小生成树的内部节点数量是
，而在 8-N 中是
。由于大多数这些高优先级边在插入优先队列后立即被移除，因此在优先队列中处理它们的计算成本是低效的。
另一方面，排名较低的边具有较高的队列时间和较高的
。边的队列时间越高，它们就越会对优先队列操作的计算成本产生负面影响，通过增加优先队列中的项目数量。α树洪水算法中的问题在于，大多数这些排名较低的边是残余边。它们被插入到优先队列中，并留在那里，直到 α 树构建完成。这对于具有非恒定时间操作的优先队列（如堆队列）的计算成本有重大影响。我们在图 4 中的点处设置了阈值
，这些点是残余边分布开始的地方。正如预期的那样，8-N 中的
小于 4-N 中的
，因为在 8-N 中有更多的边，而构建 α 树内部节点的边的数量保持不变（
）。
实际上需要优先排队的边是在
范围内的边，这大约是所有边的 10-15%。这不是 LDR 或 HDR 中的问题，因为分层队列可以以恒定时间处理插入和删除。然而，在 XDR 中情况并非如此，因为分层队列在该范围内不可用。因此，需要改进方法来处理
以下的权重排名和
以上的边，以提高 XDR 图像的 α 树算法的效率。最简单的解决方案是为
，
和
分别制作不同的队列，但这并不可行，因为除非边已排序，否则通常无法使用 ranke。此外，
和
在构建 α 树之前也是未知的。因此，为了改进 α 树中的优先排队，我们需要一种新的优先队列算法，该算法只处理
范围内的边，而无需对边进行排序，也无需事先知道
和
的值。
C. 优先队列缓存
在本节中，我们探讨如何处理优先队列中的高优先级边。如前一节所述，高优先级边是那些低 α 值的边，它们在插入优先队列后很快就会从队列中删除。我们提出了一种优先队列缓存，它在一个小型数组中存储数量有限的最高优先级边，以绕过传统基于比较的优先队列操作中的非恒定时间插入和删除操作。
图 4 展示了在具有大小 L 的缓存的优先队列中 (a) 插入和 (b) 删除的工作原理。缓存本质上是一个非常小的优先队列，它在两个操作中始终具有比主优先队列更高的优先级。插入操作始终首先尝试将新项目放入缓存中，当缓存满时，项目才会被推入主队列。同样地，删除操作首先从缓存中移除项目，当缓存为空时，才从队列中移除项目。大小 L 应该是一个非常小的数字，以保持缓存插入和删除成本低廉，但又足够大以存储所有高优先级边。我们通过实验发现，在大多数情况下 L = 12 是合理的。
通过在优先队列中使用缓存，高优先级边可以快速被处理，因为它们只由缓存处理，而不是队列。这是一个巨大的优势，特别是当队列操作成本高昂和/或有许多高优先级边，如在 4-N 中时。尽管缓存可以采用任何优先队列数据结构，但我们发现一个简单的排序数组最为高效。
D. 分层堆优先队列
在本节中，我们提出了一种新的分层堆优先队列，它通过以下三种方式优化 α 树洪水算法中的优先排队：1) 通过使用未排序数组处理低优先级边，减少残余边的优先队列插入时间复杂度；2) 通过使用优先队列缓存，减少高优先级边的插入和删除时间复杂度；3) 通过使用多个四元堆队列而不是单个二叉树，保持堆队列的深度较小。HHQ 的数据结构类似于分层队列和堆队列，并且它具有两种队列的优势：它具有分层队列中的低插入和删除计算成本，并且它可以处理 XDR 输入，就像堆队列一样。
HHQ 有一个按其 q 水平升序排列的队列的分层数组。HHQ 中的项目根据其 α 值存储在这些队列之一中。这类似于分层队列 [21]，但在分层队列中 α 值直接用作队列索引，而在 HHQ 中我们采用 α 值的对数来计算 q 水平：
参数 d 控制队列的级别数量。采用 α 值的对数的优势在于，即使 α 的动态范围很高，我们也可以保持队列数量的可行性，从而消除了分层队列的最大劣势之一。然而，不同的 α 值的项目可以存储在同一个队列中，因为不同的 α 值可以被下取整到相同的 q 水平。我们在每个级别上使用四元堆队列对项目进行排序，但我们只对高优先级的 q 水平（q 水平 < qthr）进行排序，而那些在低优先级的 q 水平的队列则保持未排序。这是因为在 α 树算法中，队列中的低优先级项目最有可能成为残余节点，我们不需要从队列中移除它们。
图 5 描述了 HHQ 中优先队列操作的工作方式。图 5(a) 显示了一个存储 15 个项目的 HHQ，这些项目在六个不同的 q 水平上。每个项目上的数字表示它们的 α 值，这些值用于计算它们的 q 水平。在这个例子中 qthr = 4，这意味着只有当它们的 q 水平小于 4 时，队列才被排序为四元堆队列。图 5(b) 显示了将 α = 11 的项目插入图 5(a) 中的队列。该项目被插入到 q 水平 = 3 的排序队列中，因为 q 水平 = ⌊d log2(α + 1)⌋ = 3（在这个例子中 d = 1）。图 5(c) 显示了插入 α = 41 的项目的队列。这个项目被插入到 q 水平 = 5 的未排序数组中。图 5(d) 显示了从队列中移除顶部项目。q 水平 = 0 的四元堆队列因此变空，于是 top_qlevel 移动到下一个非空 q 水平，即 1。再移除八个项目后，只剩下一个 α = 8 的项目在排序队列中，如图 5(e) 所示。图 5(f) 显示了当排序队列中的最后一个项目被移除时会发生什么。由于下一个 top_qlevel 在 q 水平 = 4 是未排序数组，因此需要将其转换为排序队列，并将 qthr 增加 1。
堆队列操作的计算成本与队列的最大大小 |E| 成对数比例关系。通过将堆队列划分为具有较小大小的堆队列数组，我们通过 log4(d log2(|W| + 1)) 因子平均降低了计算成本，其中 d log2(|W| + 1) 等同于 q 水平的数量。每个堆队列的大小由计算 α 值时的 q 水平值的直方图确定。由于直方图通常不均匀，HHQ 中的堆队列具有不同的大小和不同的计算成本。我们尝试通过使直方图均衡来使计算成本均衡，但这并没有改善算法的整体时间。这可能是因为直方图均衡化并没有使队列大小均匀，由于 α 值中有大量的平局和/或非均匀分布的队列大小可能比统一的更有利，因为使用了未排序数组。
图 3 中的残余边在 HHQ 中的未排序数组中存储。这些未排序数组中的大多数在 α 树构建完成之前保持未排序状态，因为残余边的 α 值高于 α 树的根节点。因此，对于残余边的排队计算成本在插入时是恒定的，在删除时基本上是零。考虑到图 3 中的残余边数量是 4-N 中的 0.40|E| 和 8-N 中的 0.65|E|，降低排队计算复杂性可以显著提高 HHQ 操作的时间。
E. 使用分层堆优先队列的洪水 α 树算法
我们已经使用提出的分层堆优先队列（HHQ）实现了洪水 α 树算法。算法 1 是洪水 α 树算法的伪代码，它类似于文献 [20] 中的算法，但是适用于 XDR。算法 1 和文献 [20] 中的算法之间的主要区别包括：(1) 算法 1 中计算的直方图（dhist）是基于像素差异度的量化对数（来自公式 (1)），而不是 [20] 中使用的原始像素差异度；(2) 用跟踪洪水算法的节点遍历作为链表替代了 [20] 中的根级别数组（levelroot）；(3) 在 pop() 操作中（queue.pop(isVisited)）使用 isVisited 数组来丢弃冗余边（REs）。我们已经用 C++ 实现了 α 树洪水算法和 HHQ，因此本节中的伪代码采用 C++ 风格。C++ 代码可在 [30] 获得。
我们定义了一个 C++ 类用于分层堆优先队列，如下所示：
class HierHeapQueue {
HQentry cache[L]; // 缓存数组
HeapQueue **HQ; // 堆队列的数组
HQentry **UA; // 未排序数组的数组
Imgidx qthr; // 堆队列和未排序数组之间的边界：qlevel < qthr 时为堆队列，否则为未排序数组
Imgidx L; // 缓存大小
Imgidx num_queues; // 队列数量
Imgidx ∗queue_sizes; // 队列大小
double d; // from (1)
};
其中 HeapQueue 是标准的四元堆队列 [29]，Imgidx 是用于像素索引的抽象数据类型，它应该具有比 [0, |V| + |E|) 更宽的动态范围，HQentry 是一个结构体，用于存储优先队列项，如下所示：
struct HQentry {
Imgidx pidx; // 边的终点
Pixel alpha; // 边权重
};
算法 2 展示了 HierHeapQueue 类的构造函数和方法的伪代码。HIERHEAPQUEUE 是 HierHeapQueue 类的构造函数，其中类变量被设置和初始化。我们通过模拟（见附录中的图 12，可在线获取）找到了最优值：在 4-N 中为 Lin = 4, din = 45, rq = 0.15，在 8-N 中为 Lin = 13, din = 45, rq = 0.15。MINLEV 方法返回队列顶部项的 α 值。插入函数 PUSH 首先检查新项目是否应该插入缓存，如图 4(a) 所示。如果缓存已满且新项目具有比缓存最后一个项更高的 α 值，则通过调用 PushQueue 方法将新项目插入 HHQ，其算法如我们在图 5(a) 中所描述的。
POP 方法从队列中移除一个项目。正如图 4(b) 所述，POP 从缓存中移除一个项目，如果缓存因此变空，它从 HHQ 中移除一个项目以保持缓存的第一个位置被占据（行 34-38）。在从 HHQ 中移除项目之前，它通过反复调用 CHECKQUEUELEVEL 直到满足条件，确保 top_qlevel 是一个非空堆队列（即，top_qlevel < qthr 且 HQ[top_qlevel].get_cursize() > 0）。CHECKQUEUELEVEL 是一个方法，用于检查 top_qlevel 是否是一个堆队列，如果是未排序数组，则将其转换为堆队列，如图 5(c) 所述（行 58-64）。
当从未排序数组转移到堆队列时，子程序会检查由项目指向的像素是否已经被访问，通过检查 isVisited。如果像素已经被访问，这意味着存在另一条具有更低 α 值的路径连接了正在处理的项目对应的边的端点，因此使其成为冗余或残余边。因此，算法会丢弃指向已访问像素的项目（行 60）。我们发现丢弃 REs 对算法性能至关重要。接下来的实验结果部分显示，85-88% 的 REs 被丢弃。在行 34-38 的循环完成后，队列顶部的项目替换了缓存中的第一个位置（行 37），然后执行 POPQUEUE 以从队列中移除顶部项目。POPQUEUE 从 HQ[top_qlevel] 中移除顶部项目，并在 HQ[top_qlevel] 变空时找到一个新 top_qlevel，类似于分层队列中的删除 [21]。
III. 结果与讨论
我们已经使用C++实现了使用所提出的分层堆优先队列的α树洪水算法[30]。我们还实现了其他α树算法用于比较：联合查找（UF）[16]、使用分层队列（HierQ）的洪水[21]、堆队列（HeapQ）[27]和字典队列（TrieQ）[28]。在UF中，边缘预先使用基数排序排序，并且通过迭代排序的边缘按升序并创建与边缘端点相关联的两个子树根的联合来构建α树[16]。此外，我们使用路径压缩来加速搜索子树根[31]，并使用高达16位的联合按排名来减少树的深度[32]。使用HeapQ的洪水大多是其最大树对应算法的α树算法版本[27]，除了使用四叉树而不是二叉树来减少树的深度。在TrieQ中，我们使用了64-ary字典，其中每个表示边缘的单比特字典节点有64个子节点存储在64位数据中。由于字典数据结构旨在表示边缘的排名而不是它们的α值，因此TrieQ是本研究中唯一一个操作边缘排名而不是α值的洪水算法（见[28]和[30]的详细信息）。我们在字典的每个叶子节点下添加了一个额外的一位作为子节点，这表明了洪水的方向，尽管它几乎使字典的大小翻倍。
我们还对提出的以及其它洪水算法应用了优先队列缓存，以调查缓存如何影响其他类型优先队列的性能。由于所有优先队列在给定相同输入时应产生相同输出，因此除了trie之外，缓存与队列之间的交互应该是相同的，因为trie的操作方式不同如上所述。最优缓存大小可能因队列而异，因为队列操作的计算时间可能不同。我们使用了不同位数深度从6位到64位，大小为100 Mpix（除非另有说明）的随机生成图像，以及五个大小为120.56 Mpix的Sentinel-2 A遥感图像[33]。实验在一台装有AMD Ryzen 7 4800H CPU和64 GB内存的计算机上进行。
A. 处理速度和内存使用
图6(a)显示了在4-N上，使用不同位数深度的不同α树算法HierQ、HeapQ、TrieQ、UF和HHQ，带或不带缓存（C）以及带或不带未排序数组（UA）的随机生成图像大小为100 Mpix的处理速度和内存使用情况。优先队列缓存改善了所有类型的优先队列，特别是在所有位数深度中的HHQ和在12-24位中的HierQ。这是因为在所有位数深度中的HHQ和HDR及XDR中的HierQ具有高删除计算成本，因此通过将队列删除（O(log |W|)）替换为缓存删除（O(1)），缓存显著提高了其性能。HeapQ的运行时间也因为缓存而在所有位数深度中得到改善，因为HeapQ操作的计算复杂度为（O(log |E|)），这与位深度无关。TrieQ受益于缓存最少。我们推测这是因为TrieQ已经具有相当低的插入和删除计算成本。提出的HHQ + C在16位以上的表现明显优于其他任何α树算法。它在32位的处理速度为5.46 Mpix/s，在64位的处理速度为4.79 Mpix/s，而最佳的传统α树算法（HeapQ）在32位和64位的处理速度分别为1.59 Mpix/s和1.52 Mpix/s。
图6(b)显示了8-N中α树算法的运行时间。缓存仍然改善了优先队列的时间，但性能提升不如4-N高。这是因为受益于缓存的高优先级边缘较少：8-N中的|E|的25%与4-N中的45%相比。8-N中非RE的比例大约是4-N中的一半。在联合查找算法中，这不是一个巨大的问题，因为边缘是按α值的顺序处理的，大多数非RE具有比其他更低的α值。然而，在洪水算法中，所有访问像素的入边都必须在PUSHNEIGHBORS中插入到优先队列中，因此有大量的多余边缘对洪水算法有巨大的负面影响。对于堆和字典队列来说，影响尤其严重，因为它们在队列操作中的计算成本更高：使用这些队列的洪水算法在8-N中的运行时间比4-N中的慢了大约两倍。使用分层和HHQ的洪水算法也变慢了，但程度较小（约35-50%），因为这些队列在插入额外边缘时不会受到太大影响，因为它们在队列插入中的计算成本非常低。提出的算法在32位的处理速度为3.41 Mpix/s，在64位的处理速度为2.94 Mpix/s，而最佳的传统α树算法（联合查找）在32位和64位的处理速度分别为0.61 Mpix/s。
图6(c)和(d)分别显示了在4-N和8-N中不同位数深度的α树算法的内存使用情况。由于缓存对内存使用的影响可以忽略不计，我们在这里省略了没有缓存的算法。使用第II-E节中的HQentry结构的HierQ和HHQ与其它算法相比具有更高的内存使用，因为一个HQentry项目必须同时存储α值和要访问的像素索引，而在UF、HierQ和TrieQ中，这些之一不需要显式存储。HHQ的内存使用比HeapQ高，因为它需要额外的指针到不同级别队列的队列，除了HQs和UAs本身。在我们的TrieQ洪水算法实现中，使用了额外的临时内存来跟踪从边缘到其排名的映射，因此TrieQ在8-N和4-N的64位中具有最高的内存占用，因为随着连通性从4-N变为8-N，临时内存的大小翻倍。HeapQ和HierQ在6位和8位中的内存使用显著降低，因为它们通过使用树大小估计（TSE）[20]来预测冗余节点的数量，从而减少了内存使用。TSE可以应用于任何LDR中的α树算法，但由于HierQ在LDR中的时间和内存使用方面都大大优于其他算法，我们没有在其他算法上实现TSE。UF使用按排名联合，这需要额外的内存空间来跟踪每个节点的排名，只有当位深度低于或等于16位时，因为具有相同α值的节点的频率在超过16位时显著降低。这就是为什么UF的内存从16位降低到18位的原因。
图7显示了α树算法的运行时间，作为图像大小从2.25 Mpix到64 Mpix的函数。图7(a)-(d)显示了4-N中α树算法的运行时间，分别为(a) 8位、(b) 16位、(c) 32位和(d) 64位，图7(e)-(h)显示了8-N中的运行时间，分别为(e) 8位、(f) 16位、(g) 32位和(h) 64位。UF、TrieQ和HeapQ的时间复杂度为O(|E|log|E|)[16], [27], [28]，HHQ的时间复杂度也是O(|E|log|E|)，因为它也使用堆队列。HierQ的时间复杂度为O(|W||E|)[21]，因此它的运行时间随着位深度的增加呈指数增长。虽然与大多数其他算法具有相同的时间复杂度，但HHQ在除8位HierQ占优之外的所有位深度中都有更好的时间。
B. 对提出的分层堆优先队列和优先队列缓存的分析
在本节中，我们对提出的分层堆优先队列（HHQ）和优先队列缓存进行了实证分析。我们通过跟踪在 HHQ 中执行 push 和 pop 操作时的队列中项目数量（Qsize）与平均内存移动次数（NMMs）的关系，对 HHQ + C 进行了实证复杂性分析。图 8 展示了在 4-N 连通性下，使用 1M 像素大小的随机生成图像构建 α 树时，HHQ + C 和简单二叉堆队列在 push 和 pop 操作中的 NMMs。
图 8(a) 显示了 HHQ 的 push 操作在每个 Qsize 上的 NMMs 是 O(1)，并且非常平坦。这可能是由于使用缓存和未排序数组（UAs）的低成本 push 操作，以及由于 HHQ 中大量的级别和在 UAs 转换为 HQs 时删除冗余边（第 60 行算法 2），保持了较小的 HQ 大小。图 8(b) 显示了 HHQ pop 操作的 O(1) 平均复杂性。pop 操作的 NMMs 在高 Qsizes 时显示出高峰，最高的峰值位于 Qsize = 0.6 M 附近。最高峰代表了将大量项目的未排序数组转换为 HQs。此点之后的 NMMs 一直保持高位，因为这些 pop 操作大部分是在一个大的 HQ 而不是一个小的或缓存中执行的。值得注意的是，最高峰之后的 NMMs 有一个周期性模式，这可能来自于每层的 HQ 逐个被清空。
除了复杂性分析之外，我们还调查了通过改变 HHQ 中的队列数量和缓存大小，提出的 HHQ 和优先队列缓存如何加速 α 树算法的处理速度的内部操作和统计数据。图 9 展示了在 1M 像素大小的 64 位随机生成图像上运行 α 树算法时 HHQ 的操作统计数据。图 9(a) 展示了 HHQ 中堆队列中的项目移动次数。这代表了已经推入 HHQ 中的项目被移入或移出其堆队列之一。它不计算推入或弹出 HHQ 的项目，因为这些计数是恒定的，与队列的性能无关。推入或从缓存或 UA 弹出的项目被计为移动。由于我们使用了 64 位图像，|W| = 2^64 并且 log2(|W|) = 64 在这里。当 HHQ 中的队列数量增加时，项目移动次数呈指数衰减，这主要是由于更多的冗余边存储在 UAs 而不是 HQs，感谢 HHQ 中足够数量的队列。如果一个冗余边存储在与它连接到同一个像素的非冗余边相同的 UA 中，则在算法 2 中的 CHECKQUEUELEVEL 期间需要对冗余边进行排序。随着 HHQ 中队列数量的增加，冗余边被排序的概率降低，因此项目移动次数随着队列数量的增加呈指数衰减。此外，项目移动次数的减少也得益于堆队列中四元树的较小深度，尽管这个影响较小。这就是为什么没有 UA 的 HHQ 比 HeapQ 表现得更好的原因，如图 6 所示。当缓存添加到 HHQ 中时，项目移动次数略有增加，无论是在 4-N 还是 8-N 中。这是由于当 "缓存未命中" 发生时从缓存推入队列的项目，或者从 HHQ 中弹出项目以填充空的缓存。
图 9(b) 展示了在 HHQ 中执行的级别检查次数。我们定义级别检查为在队列的层次结构中检查一个级别是否为空。算法 2 中的 CHECKQUEUELEVEL 执行级别检查，每次执行 POPQUEUE 时至少调用一次。缓存通过几个数量级减少了级别检查次数，无论是在 4-N 还是 8-N 中。这种巨大的减少在级别检查次数上来自于高优先级边导致的 HHQ 的 top_qlevel 波动。例如，当一个 α = 0 的边进入一个没有缓存的 HHQ，其 top_qlevel 为 1000 时，该边将存储在级别 0 的 HQ 中，并且由于公式 (1) 中的 qlevel = d × log2(1 + α) = 0，top_qlevel 将更新为 0。这条边将在下一个 POP 操作中立即被弹出，并且在边 α = 0 离开队列后，CHECKQUEUELEVEL 必须检查 1000 个空级别，直到 top_qlevel 一路爬回到 1000。在 HHQ 中有一个缓存通过在缓存而不是 HQs 中排队高优先级边来解决这个问题。缓存作为一个 "防波堤"，保护 HHQ 免受边的波动，防止 top_qlevel 随着进入 HHQ 的边的 α 值的高频波动而波动。由于缓存，级别检查次数的显著减少允许 HHQ 拥有更多的队列，从而进一步降低计算成本。即使是大小为 1 的缓存也能显著减少级别检查次数，如图 9(d) 所示。然而，小尺寸的缓存会增加由于缓存溢出或清空导致缓存和 HQs 之间频繁移动项目的 HHQ 中的项目移动次数。增大缓存的大小可以缓解这个问题，但更大的缓存尺寸会导致缓存内项目移动的计算成本更高。最优的缓存大小是一个折衷的尺寸，它在级别检查次数、HQs 中的项目移动次数和缓存中的项目移动次数之间取得平衡。我们发现最优的缓存大小通常在 4 到 20 之间，这取决于优先队列的类型和连通性。有关详细信息，请参阅附录中的图 12，可在线获取。在 HHQ 中拥有缓存也使 HHQ 的实现更容易。如果没有缓存，如果第一批边的所有 α 值都很高，就可能过早地将低优先级的 UAs 转换为 HQs，这将显著降低 HHQ 的速度，因为使用 UAs 的好处减少了。不使用缓存避免这一点并非易事，因此可以说缓存是 HHQ 的一个至关重要的部分。
图 9(c) 显示了 pRE_sorted，在缓存或 HQs 中排序的冗余边（REs）的份额。pRE_sorted 的定义如下：
显然，我们希望有一个低的 pRE_sorted。当队列数量为 1 时，即 HHQ 变成 HeapQ 时，pRE_sorted 变为 1。随着队列数量的增加，pRE_sorted 呈指数下降，使用缓存也可以略微降低 pRE_sorted，因为在缓存中排序的 REs 不计入 pRE_sorted。使用最优参数（见附录中的图 12，可在线获取）的 pRE_sorted 值为 15% 无缓存和 12% 有缓存，这意味着 HHQ 以 O(1) 的方式处理了 85-88% 的 REs。
图 9(d) 展示了缓存大小对 HHQ 统计数据的影响。随着缓存大小的增加，级别检查呈指数下降，从 0 增加到 1 时减少了 75%。然而，小尺寸的缓存增加了 8-N 中 HQs 内的项目移动次数。这是因为当缓存尺寸较小时，由于更高的缓存溢出机会，缓存中的项目需要更频繁地转移。我们定义了缓存未命中、缓存命中和其他与缓存相关的统计数据如下：
