在没有union-find数据结构的情况下实现CCL (Connected Component Labeling)算法？

Question

各位程序员，大家好！

一周前，我被指派了实现连通分量算法的任务，主要是从图像中提取对象的数量。

你可以在这里阅读更多关于算法的信息(https://en.wikipedia.org/wiki/Connected-component_labeling)，我尝试实现的变体是两遍一。

这是我目前的尝试：

% ------------------------------------------------------------------------------
% -> Connected Component Labeling (CCL) Algorithm
% -> 4-Connectivity Version
% ------------------------------------------------------------------------------

% ------------------------------------------------------------------------------
% - [ Pre-Scan Code To Get Everything Ready ] -
% ------------------------------------------------------------------------------
% Starting With A Clean (Workspace) And (Command Window).
clear, clc;

% Instead Of Loading An Actual Image, We Are Creating A Matrix Of Zeros And Ones, Representing A Binary Image.
originalImage = [ ...
                0 1 0
                1 0 1
                0 1 0 ];

% Creating A Bigger Matrix That We Will Use To Store The Original Image In Its Middle, This Will Help Us Eliminate Border Checking In The Raster Scan.
binaryImage = zeros(size(originalImage) + 2);

% Copying The Pixels From The Original Image Into The Middle Of The Larger Matrix We Created.
binaryImage(2:size(originalImage, 1) + 1, 2:size(originalImage, 2) + 1) = originalImage;

% Getting The Number Of Rows (Height) And Number Of Columns (Width) Of The Binary Image.
[imageRows, imageColumns] = size(binaryImage);

% Creating A Matrix The Same Dimensions As The Binary Image In Which The Labeling Will Happen.
labeledImage = zeros(imageRows, imageColumns);

% Creating A Label Counter That We Will Use To Assign When We Create New Labels.
labelCounter = 1;

% ------------------------------------------------------------------------------
% - [First Scan: Assigning Labels To Indices] -
% ------------------------------------------------------------------------------
% Going Over Each Row In The Image One By One.
for r = 1:imageRows
   % Going Over Each Column In The Image One By One.
   for c = 1:imageColumns
       % If The Pixel Currently Being Scanned Is A Foreground Pixel (1).
       if (binaryImage(r, c) == 1)
           % Since We Are Working With 4-Connectivity We Only Need To Read 2 Labels, Mainly The (Left) And (Top) Labels.
           % Storing Them In Variables So Referencing Them Is Easier.
           left = labeledImage(r, c - 1);
           top = labeledImage(r - 1, c);
           % If Left == 0 And Top == 0 -> Create A New Label, And Increment The Label Counter, Also Add The Label To The Equivalency List.
           if (left == 0 && top == 0)
               labeledImage(r, c) = labelCounter;
               labelCounter = labelCounter + 1;
           % If Left == 0 And Top >= 1 -> Copy The Top Label.
           elseif (left == 0 && top >= 1)
               labeledImage(r, c) = top;
           % If Left >= 1 And Top == 0 -> Copy The Left Label.
           elseif (left >= 1 && top == 0)
               labeledImage(r, c) = left;
           % If Left >= 1 And Top >= 1 -> Find The Minimum Of The Two And Copy It, Also Add The Equivalent Labels To The Equivalency List, So We Can Fix Them In The Second Scan.
           elseif (left >= 1 && top >= 1)
               labeledImage(r, c) = min(left, top);
           end
       end
   end
end

% ------------------------------------------------------------------------------
% - [Second Scan: Fixing The Connected Pixels But Mismatched Labels] -
% ------------------------------------------------------------------------------
for r = 1:imageRows
   for c = 1:imageColumns

   end
end

第一遍通过了，没有任何问题，我已经对它进行了多次测试，但是我不知道如何实现第二遍，在第二遍中，我必须修复标签矩阵中的等价标签。

我确实在网上做了研究，首选的方法是使用联合查找(不相交集合)数据结构来存储标签之间的等价物。

但是，由于我使用的是MATLAB，并且union-find数据结构没有实现，所以我必须自己实现它，这很麻烦，而且由于MATLAB是一种解释型语言，需要大量的时间和艰苦的工作。

因此，我对实现第二遍而不必使用union-find数据结构的想法持开放态度。

提前感谢！

Answer 1

如果你不想使用联合查找，那么你真的应该使用洪泛填充每个组件的算法(Wikipedia中的另一个算法)。

然而，Union-find既不难也不慢，我会用它来解决这个问题。要进行简单快速的实现，请执行以下操作：

• 使用与图像形状相同的整数矩阵来表示集合--矩阵中的每个整数表示相应像素的集合。
• 整数x表示集合如下:如果x< 0，则它是大小为-x的根集。如果为x>=0，则它是具有父集x(即，行x/宽度，列x%宽度)的子集。将所有集初始化为-1，因为它们都是从大小为1的根开始的。
• 使用按大小并集和路径压缩