这个连通分量标记算法是新的吗？

Question

很久以前，我做了一个游戏，其中需要一种连接组件标记来实现 AI 部分。我当时不知不觉用了two-pass算法

最近，我了解到我可以使用基于位扫描的方法使它们更快。它使用每像素 1 位数据作为输入，而不是典型的每像素字节输入。然后它使用 BSF 指令找到每个扫描线中的每个线性块。请看下面的代码。 Cut 是一个结构，它保存扫描线中位 1 的线性块的信息。

Cut* get_cuts_in_row(const u32* bits, const u32* bit_final, Cut* cuts) {
    u32 working_bits = *bits;
    u32 basepos = 0, bitpos = 0;
    for (;; cuts++) {
        //find starting position
        while (!_BitScanForward(&bitpos, working_bits)) {
            bits++, basepos += 32;
            if (bits == bit_final) {
                cuts->start_pos = (short)0xFFFF;
                cuts->end_pos = (short)0xFFFF;
                return cuts + 1;
            }
            working_bits = *bits;
        }
        cuts->start_pos = short(basepos + bitpos);

        //find ending position
        working_bits = (~working_bits) & (0xFFFFFFFF << bitpos);
        while (!_BitScanForward(&bitpos, working_bits)) {
            bits++, basepos += 32;
            working_bits = ~(*bits);
        }
        working_bits = (~working_bits) & (0xFFFFFFFF << bitpos);
        cuts->end_pos = short(basepos + bitpos);
    }
}

首先，它使用汇编BSF指令找到第一个位1出现的位置。找到后，使用位反转和位掩码找到第一个位0出现在该位置之后，然后重复这个过程。

得到每条扫描线中所有1s的线性块（我更喜欢称它们为'cuts'）的起始位置和结束位置后，它以CCL方式对其进行标记。对于第一行，每个剪辑都有不同的标签。

对于其余行中的每个切割，它会检查是否有先连接到它的上切割。如果没有上切线连接到它，它就会得到新的标签。如果只有一个 upper cuts 连接到它，它会得到标签的副本。如果许多上切线连接到它，这些标签将被合并，它得到合并后的标签。这可以使用上块和下块的两个进度指针轻松完成。这是执行该部分的完整代码。

Label* get_labels_8c(Cut* cuts, Cut* cuts_end, Label* label_next) {
    Cut* cuts_up = cuts;
    
    //generate labels for the first row
    for (; cuts->start_pos != 0xFFFF; cuts++) cuts->label = [GET NEW LABEL FROM THE POOL];
    cuts++;

    //generate labels for the rests
    for (; cuts != cuts_end; cuts++) {
        Cut* cuts_save = cuts;
        for (;; cuts++) {
            u32 start_pos = cuts->start_pos;
            if (start_pos == 0xFFFF) break;

            //Skip upper slices ends before this slice starts 
            for (; cuts_up->end_pos < start_pos; cuts_up++);

            //No upper slice meets this
            u32 end_pos = cuts->end_pos;
            if (cuts_up->start_pos > end_pos) {
                cuts->label = [GET NEW LABEL FROM THE POOL];
                continue;
            };

            Label* label = label_equiv_recursion(cuts_up->label);

            //Next upper slice can not meet this
            if (end_pos <= cuts_up->end_pos) {
                cuts->label = label;
                continue;
            }

            //Find next upper slices meet this
            for (; cuts_up->start_pos <= end_pos; cuts_up++) {
                Label* label_other = label_equiv_recursion(cuts_up->label);
                if (label != label_other) [MERGE TWO LABELS]
                if (end_pos <= cuts_up->end_pos) break;
            }
            cuts->label = label;
        }
        cuts_up = cuts_save;
    }
    return label_next;
}

在此之后，可以使用每个扫描线的这些信息来直接制作标签数组或他想要的任何输出。

我检查了这个方法的执行时间，然后我发现它比我以前使用的两次扫描方法快得多。令人惊讶的是，即使输入数据是随机的，它也比二次扫描快得多。显然，位扫描算法最适合结构相对简单的数据，其中扫描线中的每个块都很大。它并非设计用于随机图像。

让我感到困惑的是，几乎没有人谈论过这种方法。坦率地说，这似乎并不是一个很难想出的主意。很难相信我是第一个尝试它的人。

也许我的方法比原始的二次扫描方法好，但比基于二次扫描思想的更先进的方法差，所以无论如何都不值得一提。

但是，如果二次扫描法可以改进，位扫描法也可以。我自己发现了 8-connectivity 的一个很好的改进。它分析相邻的两条扫描线，我使用位或指令将它们合并。您可以找到完整代码和有关它们如何工作的详细说明 here。

我知道有一个名为 YACCLAB 的 CCL 算法基准。我将使用最佳 CCL 算法测试我的算法，看看它们到底有多好。在此之前，我想在这里问几件事。

我的问题是，

我发现的这些算法真的很新吗？仍然很难相信没有人想过使用位扫描的 CCL 算法。如果它已经是一件事，为什么我找不到任何人谈论它？基于位扫描的算法是否被证明是错误的并且被遗忘了？
如果我真的找到了新的算法，接下来我该怎么做？当然我会在像 YACCLAB 这样更可靠的系统中测试它。我在问我接下来应该做什么。我应该怎么做才能让这些算法挖掘并传播它们？

Answer 1

到目前为止，我有点怀疑

我的推理太长了，无法发表评论，所以我们来了。有很多东西要打开。我非常喜欢这个问题，尽管它可能更适合 computer science 网站。

问题是，这个问题有两层：

是否发现了新算法？
位扫描部分呢？

你把这两者结合起来，所以首先我会解释为什么我想分开考虑它们：
算法是一组与语言无关的步骤(more formal definition)。因此，即使不需要位扫描，它也应该可以工作。
另一方面，位扫描我认为是一种优化技术——我们使用的是计算机可以适应的结构我们的性能提升。

除非我们将这两者分开，否则问题会变得有点模糊，因为可能会发生几种可能的情况：

该算法是新的和改进的，位扫描使其更快。那太棒了。
该算法只是 “两次通过” 或类似说法的一种新说法。如果它超过基准，那仍然是好的。在这种情况下，可能值得将其添加到 CCL 的库中。
该算法非常适合某些情况，但在其他情况下却以某种方式失败（速度方面，而不是校正方面）。这里的位扫描使得比较困难。
该算法非常适合某些情况，但在其他情况下完全失败（产生不正确的结果）。你只是还没找到反例

让我们假设 4 不是这种情况，我们想在 1 到 3 之间做出决定。在每种情况下，位扫描都会使事情变得模糊，因为它很可能会加快速度——因此在某些情况下，即使是较慢的算法也可能胜过更好的算法。

所以首先我会尝试删除位扫描并重新评估性能。快速浏览后，CCL 的算法似乎具有线性复杂性，具体取决于图像大小——您需要至少检查每个像素一次。休息是为尽可能降低常量而进行的斗争。（通过次数，要检查的邻居数量等）我认为可以安全地假设，你不能比线性做得更好 - 所以第一个问题是：你的算法是否通过乘法常数提高了复杂性？由于算法是线性的，因此该因素直接转化为很好的性能。

第二个问题那就是：位扫描是否进一步提高了算法的性能？

另外，既然我已经开始考虑了，那么棋盘模式和4-connectivity呢？或者，一个 3x3 的棋盘交叉用于 8 连接。

这个连通分量标记算法是新的吗？

Is this connected-component labeling algorithm new?

c++

algorithm

optimization

connected-components

到目前为止，我有点怀疑