0

私は現在、データベース システム (C++ で記述) に CCL アルゴリズムを実装する任務を負っています。このアルゴリズムは、指定された多次元配列のしきい値を超えるすべての値にラベルを割り当て、隣接するラベル付きの値には同じラベルが付けられます。

基本的な CCL アルゴリズムのコーディングは難しくありませんが、私のドメインでは、入力配列はデータベースの複数のインスタンスにランダムに分割されています。私の CCL オペレーターが呼び出されると、各インスタンスは、担当するデータのチャンクに対して操作を実行し、そのローカル CCL 結果を返します。次に、これらのローカル結果がマージされて、最終結果が生成されます。

実行時に、どのインスタンスが配列の特定の部分を担当しているのかわかりません。インスタンスは、最後のマージ手順まで互いに通信できません。

-=-=-=-

現在、私は次のことを行うことでこれを機能させています。

  1. 各インスタンスは、配列内の項目数と同じサイズのブール値の配列を作成し、すべての値を FALSE に設定します。

  2. 各インスタンスは、担当する値を調べ、それらの値がしきい値を超えているかどうかを確認します。そうであれば、ローカル配列の対応するブール値を TRUE に変更します。

  3. インスタンスはすべてその配列をコーディネーターに送信します。コーディネーターは OR を使用して結果を結合し、最終的なブール ベクトルを作成します。

  4. コーディネーターは、既にラベル付けされている値をスキップして、配列内のすべての値を調べます。値にラベルが付けられておらず、その値に対応するブール値が true の場合、新しいラベルが割り当てられ、すべての近隣 (および近隣の近隣など) に同じラベルが再帰的に割り当てられます。

  5. ラベルのベクトルが返されます。

上記のアルゴリズムは機能しますが、複数のインスタンスを持つことを利用しているのはしきい値の計算だけです。この実装は単純にすべてを収集してコーディネーター上でスキャンするため、そもそも複数のインスタンスを使用するという点を無効にします。

-=-=-=-

基本的に、このアルゴリズムは自動的に分割統治アルゴリズムになりますが、分割は完全に無作為に制御できません。

各インスタンスで CCL の両方のスイープを実行し、コーディネーターでこれらのローカル CCL 結果を結合することで、この分割を利用したいと考えています。つまり、2 つのインスタンスが互いに隣接するラベルのグループを生成する場合、すべての値を再度スキャンすることなく、これら 2 つのラベルを結合したいと考えています。このイタリック体のポイントは、私たちに最も問題を引き起こしているものであり、どのように進めればよいかかなり迷っています. 調査するのに適したアルゴリズムまたはデータ構造の提案があれば、大歓迎です。

4

1 に答える 1

0

隣接連結成分 (グラフ連結成分とは対照的に) では、隣接 (隣接するピクセル) のすべてのペアのセットを調べる必要があります。

あれは、

  • 隣接する点のペアでセットを定義します。
    • { ((x1, y1), (x2, y2)) }そのために
      • 4 コネクティビティの場合:(abs(x2 - x1) + abs(y2 - y1)) <= 1および(x1 != x2 && y1 != y2)
      • 8 コネクティビティの場合:max(abs(x2 - x1), abs(y2 - y1)) <= 1および(x1 != x2 && y1 != y2)

理解の次のステップでは、同値関係を知る必要があります。特に、次の条件を満たす必要があります。

  • 反射性
  • 対称
  • 推移性

これら 3 つの要件から興味深い結果が得られます。

  • (a, b)、(b, c)、(c, d)、(e, f) などの同値関係の部分的なリストが与えられたとします。
  • このリストを並べ替えたり、「同等の」同値関係 ((a, b) と (b, c) が既に存在する場合に (a, c) など) を挿入したりしても、分割には影響しないことに注意してください。

重要なのは、以下で説明する「Disjoint-Set」のアルゴリズム インターフェイスが、まさに同値関係のリストであるということです。したがって、この同値関係のリストを別の方法で処理しても、同じ結果が得られます。

連結成分を計算および処理するアルゴリズムを表現および説明するには、 Disjoint-Setを学習する必要があります。

Disjoint-Set の実際の実装を学び、連結要素アルゴリズムから実際にどのように使用されるか (呼び出されるか) も学ぶ必要があります。

その後、理解の抽象化レベル、つまり Disjoint-Set の抽象的な概念 (アルゴリズム インターフェイス) を高める必要があります。この抽象化を学んだ後、通常とは異なる方法でDisjoint-Set を再実装できるようになります。

  • 構築段階では、Union関数のみをメイン ループから呼び出す必要があります。
  • 関数はFind関数内でのみ使用されUnionます。
  • Union( (x1, y1), (x2, y2) )したがって、メッセージ呼び出しのストリームにシンクを提供することにより、Disjoint-Set の操作を抽象化できます。
  • これらのメッセージ呼び出しは、非同期、キュー、ランダムに並べ替え、バッチ処理することができますが、そのようなすべての呼び出しが最終的に完全に処理される限り、それらを処理したいと考えています。
  • Unionこれは、呼び出しをキューに入れる前に 2 つのノードがすでに同じラベルであるかどうかのチェックが行われないため、への呼び出しが冗長になります。この問題については、次の部分で扱います。

ここで、これらのUnionメッセージの処理をスケジュールする方法を紹介します。

ノードが異なるマシンに分散されているとします。

  • 次のように、隣接するピクセルのペアのセットを分割{ ((x1, y1), (x2, y2)) }します。
    • 各マシンについて、同じマシン上に存在する隣接するピクセルのペアのサブセットを見つけたいと考えています。
    • その後、他のすべてのサブセット (2 つの別々のマシンに存在する隣接するピクセルのペア) が必要になります。

異なるマシン間で Union-Find を処理するには、単純に *Union同じマシンの隣接するピクセルのペアのセットからメッセージを生成します。 * 次に、Unionメッセージをフィルタリングして冗長なものを削除します。*Union隣接するピクセルのペアの異なるマシン セットからメッセージを生成します。* 同じマシン メッセージの結果に対して異なるマシン メッセージを実行します。

この回答は非常に抽象的な方法で書かれています。より具体的な回答には、問題に関する詳細、特に「完全かつ制御不能なランダムなパーティション分割」に関する部分が必要になるためです。

于 2014-08-17T22:43:23.087 に答える