Connected Component Labeling で Disjoint Sets を使用するのに苦労しています。私は多くの例と、Bo Tian が Disjoint Sets の非常に優れた実装を C++ リンク リストとして提供したこの質問についても調べました。私は自分のプログラムに Connected Component ラベル付け (ラベルは単純な整数) を既に実装していますが、セットがばらばらなラベル間で同等性を解決するのは非常に困難です。
Bo Tianの実装を使用して、誰かが私を助けることができますか? 他の人がこの時点に来たら、それも役立つと思います。
編集
私のアルゴリズムは画像を調べ、異なるラベルを持つ 2 つの接続されたピクセルの 2 つのラベルを見つけると、「等価レジストリ」にメモを作成する必要があります (これは Disjoint set forest になります)。画像全体をループした後、(画像を 2 番目にパスする) レジストリを見て、同等のラベルを持つこれらのピクセルをセットの最小値にマークすることで、同等性を解決する必要があります。
素集合フォレストは、次の2つの操作を提供します。
互いに素なフォレストは、主に、オブジェクトのグループを異なるクラスターのファミリーに分割するために使用されます。各クラスターは、互いに素です（つまり、各オブジェクトは最大で1つのグループに含まれます）。素集合フォレストを使用すると、各グループに含まれるオブジェクトを効率的に判断したり、（およそO（n）時間で）各オブジェクトのクラスターIDを決定したりできます。
素集合フォレストを使用するには、まず各オブジェクトを独自のクラスターに配置します。その時点から、2つの異なるオブジェクトが同じクラスター内にあることをマークするたびに、和集合演算を使用してそれらをリンクします。最後に、各ポイントでfindを呼び出して、それが属するクラスターを判別し、そこからすべてが属するグループを読み取ることができます。
お役に立てれば！
おっしゃる通り、連結集合にラベルを付けるだけで作業は半分しか終わりません。同値を使用して素集合を見つけることも同様に難しい部分です。私は正確なシナリオに直面しました。
互いに素な集合を (ラベル付け後に) 見つける 1 つの方法は、Union-Findアルゴリズムを使用することです。次の記事をご覧ください。ばらばらなセットのラベル付けと検索がどのように実装されているかをゼロから理解できます。サンプルの入力行列と出力行列の図も示されています。
DJS でこのチュートリアルを確認してください。唯一の変更点は、ユニオン中に大きいものから小さいものに接続する必要があるため、ルートは常にセットの最小値です。
互いに素なセットを使用した連結成分のラベル付けに関するブログがあります。