这种连接组件标记算法是新的吗？

Question

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

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

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的所有线性块的起始位置和结束位置之后(我更喜欢将它们称为“裁剪”)，它以CCL的方式给它们贴上标签。对于第一行，每个裁剪都有不同的标签。

对于rest行中的每一个裁剪，它首先检查是否存在连接到rest行的上切。如果没有上切连接到它，它会得到新的标签。如果只有一个上切连接到它，它将得到标签的副本。如果多个上线被连接到它，那么这些标签就会被合并，并得到合并的标签。这可以很容易地使用上块和下块的两个进展指针来完成。下面是完成该部分的完整代码。

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连接性的一个很好的改进。它分析相邻的两条扫描线，我用位或指令合并它们.您可以找到完整的代码和关于它们如何工作这里的详细说明。

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

我的问题是，

1. 我发现这些算法真的很新吗？很难相信没有人想到过使用位扫描的CCL算法.如果这已经是件事了，为什么我找不到人说呢？基于位扫描的算法被证明是不好的并且被遗忘了吗？
2. 如果我真的找到了一个新的算法，我下一步该做什么？当然，我会在像YACCLAB这样更可靠的系统中测试它。我在质疑我下一步该做什么。我应该怎样才能使这些算法得到挖掘和推广呢？

Answer 1

到目前为止，我有点怀疑

我的理由太长了，不能发表评论，所以我们来谈一谈。有很多东西要打开。我非常喜欢这个问题，尽管它可能更适合于计算机科学站点。

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

1. 发现了一种新算法吗？
2. 钻头扫描部分呢？

你把这两者结合在一起，所以首先我要解释为什么我要分别考虑它们：

算法是一组与语言无关的步骤((更正式的定义)).因此，即使不需要位扫描，它也应该工作。

另一方面，我认为位扫描是一种优化技术--我们使用的是一种计算机感到舒服的结构，它可以给我们带来性能提升。

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

1. 该算法是一种新的改进算法，且比特扫描速度更快。那就太棒了。
2. 该算法只是一种新的方式，用来表示“两次通过”或类似的东西。如果它超过了基准，那还是很好的。在这种情况下，可能值得为CCL添加一个库。
3. 该算法适用于某些情况，但在其他情况下却以某种方式失败(速度方面，而不是纠正方面)。这里的位扫描使得比较困难。
4. 该算法适用于某些情况，但在其他情况下完全失败(产生不正确的结果)。你只是还没找到反例。

假设4不是这种情况，我们希望在1到3之间作出决定。在每一种情况下，位扫描都会使事情变得模糊，因为它很可能会加速更多的事情--因此在某些情况下，即使是较慢的算法也可能优于更好的算法。

，所以首先，，我会尝试删除位扫描，并重新评估性能。快速查看后，CCL的算法似乎具有线性复杂度，这取决于图像大小--您至少需要检查每个像素一次。休息是尽可能地降低常量的斗争。(出入证数量、要检查的邻居数等)我认为这是安全的，你不能比线性做得更好-所以第一个问题是:你的算法是否通过一个乘法常数来提高复杂性？由于该算法是线性的，因此该因子直接转化为性能优良的因素。

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

而且，既然我已经开始考虑这个问题了，那么棋盘模式和4连接又如何呢？或者，一个3x3的棋盘交叉8-连接。