在二维比特阵列中寻找比特的连续区域

Question

问题

我有一个位数组,表示"瓷砖"的二维"地图".此图像提供了位数组中位的图形示例:

我需要确定数组中存在多少个连续的"区域"位.在上面的例子中,有两个这样的连续"区域",如下所示:

瓷砖必须直接位于瓷砖的N,S,E或W上才能被认为是"连续的".对角线触摸的瓷砖不计算在内.

我到目前为止

因为这些位数组可能变得相对较大(大小为几MB),所以我故意避免在我的算法中使用任何类型的递归.

伪代码如下:

LET S BE SOURCE DATA ARRAY
LET C BE ARRAY OF IDENTICAL LENGTH TO SOURCE DATA USED TO TRACK "CHECKED" BITS
FOREACH INDEX I IN S
    IF C[I] THEN 
        CONTINUE 
    ELSE
        SET C[I]
        IF S[I] THEN
            EXTRACT_AREA(S, C, I)

EXTRACT_AREA(S, C, I):
    LET T BE TARGET DATA ARRAY FOR STORING BITS OF THE AREA WE'RE EXTRACTING
    LET F BE STACK OF TILES TO SEARCH NEXT
    PUSH I UNTO F
    SET T[I]
    WHILE F IS NOT EMPTY
        LET X = POP FROM F
        IF C[X] THEN 
            CONTINUE
        ELSE
            SET C[X]
            IF S[X] THEN
                PUSH TILE NORTH OF X TO F
                PUSH TILE SOUTH OF X TO F
                PUSH TILE WEST OF X TO F
                PUSH TILE EAST OF X TO F
                SET T[X]
    RETURN T

我不喜欢我的解决方案

• 只是为了运行,它需要两倍于它正在处理的位图数组的内存.
• 在提取"区域"时,它使用位图数组的三倍内存.
• 复制品存在于"要检查的瓷砖"堆栈中 - 这看起来很丑陋,但不值得避开我现在拥有的东西.

我想看到什么

• 更好的记忆力
• 更快地处理大面积区域

---

解决方案/跟进

我重新编写了解决方案来探索边缘(根据@hatchet的建议).

这实现起来非常简单 - 并且无需完全跟踪"访问过的磁贴".

基于三个简单的规则,我可以遍历边缘,跟踪最小/最大x和y值,并在我再次到达开始时完成.

这是我使用的三个规则的演示:

Answer 1

一种方法是周边步行.给定沿着形状边缘的起点,记住这一点.

就像那一点一样启动边界框.

使用顺时针规则集行走周边 - 如果用于到达当前点的点在上方,则首先向右看,然后向下看,然后向左找到形状周长上的下一个点.这有点像解决迷宫的简单策略,你不断追随墙壁并始终向右倾斜.

每次访问新的外围点时,如果新点在其外部,则展开边界框(即跟踪最小和最大x和y.

继续,直到达到起点.

缺点:如果形状有很多单个像素的"细丝",那么随着步行回来,你将重新审视它们.

优点:如果形状具有大面积的内部占用空间,您就不必像在洪水填充中记录访问过的像素那样访问它们或记录它们.

因此,节省空间,但在某些情况下会牺牲时间.

编辑

通常情况下,这个问题是已知的,命名的,并且具有多种算法解决方案.您描述的问题称为最小边界矩形.解决此问题的一种方法是使用轮廓跟踪.我上面描述的方法属于该类,被称为摩尔邻接跟踪或径向扫描.我为他们提供的链接详细讨论了它们,并指出了一个我没有抓到的问题.有时你会在遍历整个周边之前重新审视起点.如果您的起点位于单个像素"灯丝"的某个位置,您将在完成之前重新访问它,除非您考虑到这种可能性,否则您将过早停止.我链接的网站讨论了解决这个停止问题的方法.该网站的其他页面还讨论了另外两种算法:Square Tracing和Theo Pavlidis的算法.有一点需要注意的是,这些对角线都是连续的,而你却没有,但是这应该是可以通过对基本算法进行微小修改来处理的东西.

您的问题的另一种方法是连接组件标签.但是,根据您的需求,这可能是一个比您需要的更昂贵的解决方案.

附加资源:

C++中的摩尔邻域轮廓跟踪算法