非常大的图像中的记忆效率线缝合

Question

背景

我使用Synthetic Aperture Radar卫星的非常大的数据集.这些可以被认为是一侧10k像素量级的高动态范围灰度图像.

最近,我一直在开发Lindeberg尺度空间脊检测算法的单尺度变体的应用,用于检测SAR图像中的线性特征.这是对使用方向滤波器或使用Hough变换的改进,这两种方法以前都使用过,因为它的计算成本低于其中任何一种.(我将在4月份的JURSE 2011上展示一些最新成果,如果有帮助,我可以上传预印本).

我目前使用的代码生成一个记录数组,每个像素一个,每个记录描述矩形到像素右下角的一个脊段,并由相邻的像素限定.

struct ridge_t { unsigned char top, left, bottom, right };
int rows, cols;
struct ridge_t *ridges;  /* An array of rows*cols ridge entries */

在一个条目ridges包含脊段如果正好有两个的top,left,right并bottom具有范围值0 - 128.假设我有:

ridge_t entry;
entry.top = 25; entry.left = 255; entry.bottom = 255; entry.right = 76;

然后我可以找到脊段的开始(x1,y1)和结束(x2,y2):

float x1, y1, x2, y2;
x1 = (float) col + (float) entry.top / 128.0;
y1 = (float) row;
x2 = (float) col + 1;
y2 = (float) row + (float) entry.right / 128.0;

当渲染这些单独的脊段时,我得到的图像就像这样(图像的一个非常小的角):

每条长曲线都是从一系列细小的脊段中渲染出来的.

确定包含脊段的两个相邻位置是否连接是微不足道的.如果我有ridge1(x,y)和ridge2(x + 1,y),那么如果0 <= ridge1.right<= 128 和 ridge2.left = ,它们就是同一行的一部分ridge1.right.

问题

理想情况下,我想将所有脊段拼接成线,这样我就可以迭代图像中的每一条线来应用进一步的计算.不幸的是,我发现很难找到一种算法,这种算法既低复杂又有内存效率,适合多处理(在处理真正巨大的图像时,所有重要的考虑因素!)

我考虑过的一种方法是扫描图像,直到找到一个只有一个连接的脊段的脊,然后走过生成的线,标记线上的任何脊.但是,这不适用于多处理,因为没有办法判断是否没有另一个线程从另一个方向(例如)走同一条线而没有昂贵的锁定.

读者建议采用什么方法？似乎有人会在过去想出一个有效的方法......

Answer 1

我不完全确定这是正确的，但我想我应该把它扔掉以供评论。首先，让我介绍一个无锁不相交集算法，它将构成我提出的算法的重要组成部分。

无锁不相交集算法

我假设在您选择的 CPU 架构上存在两个指针大小的比较和交换操作。这至少在 x86 和 x64 架构上可用。

该算法与维基百科页面上针对单线程情况所描述的算法基本相同，但为了安全的无锁操作进行了一些修改。首先，我们要求排名元素和父元素都是指针大小，并在内存中与 2*sizeof(pointer) 对齐，以便稍后用于原子 CAS。

Find() 不需要改变；最坏的情况是，在同时写入的情况下，路径压缩优化将无法充分发挥作用。

然而 Union() 必须更改：

function Union(x, y)
  redo:
    x = Find(x)
    y = Find(y)
    if x == y
        return
    xSnap = AtomicRead(x) -- read both rank and pointer atomically
    ySnap = AtomicRead(y) -- this operation may be done using a CAS
    if (xSnap.parent != x || ySnap.parent != y)
        goto redo
    -- Ensure x has lower rank (meaning y will be the new root)
    if (xSnap.rank > ySnap.rank)
        swap(xSnap, ySnap)
        swap(x, y)
    -- if same rank, use pointer value as a fallback sort
    else if (xSnap.rank == ySnap.rank && x > y)
        swap(xSnap, ySnap)
        swap(x, y)
    yNew = ySnap
    yNew.rank = max(yNew.rank, xSnap.rank + 1)
    xNew = xSnap
    xNew.parent = y
    if (!CAS(y, ySnap, yNew))
      goto redo
    if (!CAS(x, xSnap, xNew))
      goto redo
    return

这应该是安全的，因为它永远不会形成循环，并且总是会产生正确的联合。我们可以通过观察来证实这一点：

• 首先，在终止之前，两个根中的一个总是以指向另一个的父根结束。因此，只要不存在循环，合并就成功。
• 其次，等级总是在增加。比较 x 和 y 的顺序后，我们知道在快照时 x 的排名低于 y。为了形成循环，另一个线程需要首先增加 x 的等级，然后合并 x 和 y。然而，在写入x的父指针的CAS中，我们检查等级没有改变；因此，y 的等级必须保持大于 x。

在同时突变的情况下， y的等级可能会增加，然后由于冲突而返回重做。然而，这意味着要么 y 不再是根（在这种情况下，等级无关），要么 y 的等级已被另一个进程增加（在这种情况下，第二次循环将不起作用，并且 y 将具有正确的等级）。

因此，应该不会形成循环，并且这种无锁不相交集算法应该是安全的。

现在谈谈您的问题的应用程序......

假设

我假设山脊线段只能在其端点相交。如果情况并非如此，您将需要以某种方式更改第 1 阶段。

我还假设单个整数像素位置的共存足以连接山脊线段。如果没有，您将需要更改第 1 阶段中的数组以保存多个候选脊线段+不相交集对，并进行过滤以查找实际连接的脊线段。

该算法中使用的不相交集合结构应在其结构中携带对线段的引用。在合并的情况下，我们任意选择两个记录片段之一来表示该集合。

第一阶段：本地线路识别

我们首先将地图划分为多个扇区，每个扇区将作为单独的作业进行处理。多个作业可以在不同的线程中处理，但每个作业将仅由一个线程处理。如果山脊线段穿过某个扇区，则会将其分成两段，每个扇区对应一个线段。

对于每个扇区，建立将像素位置映射到不相交集结构的阵列。该数组的大部分内容稍后都会被丢弃，因此其内存需求不应成为太大的负担。

然后我们继续处理该扇区中的每个线段。我们首先选择一个不相交的集合，表示该线段所属的整条线。我们首先查找像素位置数组中的每个端点，看看是否已经分配了不相交的集合结构。如果端点之一已在此数组中，我们将使用分配的不相交集。如果两者都在数组中，我们对不相交的集合执行合并，并使用新的根作为我们的集合。否则，我们创建一个新的不相交集，并将该不相交集结构与对当前线段的引用相关联。然后，我们将每个端点的新不相交集的根写回到像素位置数组中。

对于扇区中的每个线段重复此过程；到最后，我们将通过一个不相交的集合完全识别出扇区内的所有线。

请注意，由于不相交集尚未在线程之间共享，因此还不需要使用比较和交换操作；只需使用普通的单线程联合合并算法即可。由于在算法完成之前我们不会释放任何不相交的集合结构，因此也可以从每线程碰撞分配器进行分配，从而使内存分配（实际上）无锁且 O(1)。

一旦一个扇区被完全处理，像素位置数组中的所有数据都将被丢弃；然而，与扇区边缘上的像素相对应的数据被复制到新的阵列并保留用于下一阶段。

由于迭代整个图像的时间复杂度为 O(x*y)，并且不相交合并实际上为 O(1)，因此该操作的时间复杂度为 O(x*y)，并且需要工作内存 O(m+2*x*y/k+ k^2) = O(x*y/k+k^2)，其中 t 是扇区数，k 是扇区宽度，m 是扇区中部分线段的数量（取决于如何线经常跨越边界，m可能会有很大变化，但永远不会超过线段的数量）。结转到下一个操作的内存为 O(m + 2*x*y/k) = O(x*y/k)

第二阶段：跨行业合并

一旦处理完所有扇区，我们就会转向跨扇区的合并线。对于扇区之间的每个边界，我们对跨越边界的线执行无锁合并操作（即，边界每一侧的相邻像素已分配给线集）。

该操作的运行时间为 O(x+y)，消耗 O(1) 内存（但是我们必须保留阶段 1 的内存）。完成后，可以丢弃边缘阵列。

第三阶段：收集线路

我们现在对所有分配的不相交集结构对象执行多线程映射操作。我们首先跳过任何不是根的对象（即，其中 obj.parent != obj）。然后，从代表性线段开始，我们从那里移出并收集并记录有关相关线所需的任何信息。我们确信一次只有一个线程正在查看任何给定的线，因为相交的线最终会出现在相同的不相交集结构中。

运行时间为 O(m)，内存使用量取决于您需要收集有关这些线段的信息。

概括

总体而言，该算法应具有 O(x*y) 运行时间和 O(x*y/k + k^2) 内存使用量。调整 k 可以在第 1 阶段进程的瞬时内存使用量与转入第 2 阶段的邻接数组和不相交集结构的长期内存使用量之间进行权衡。

请注意，我尚未在现实​​世界中实际测试该算法的性能；我也可能忽略了上面的无锁不相交集联合合并算法中的并发问题。欢迎评论:)