問題タブ [connected-components]

事前に計算された KDTree を使用して、接続されたコンポーネントの数を見つけるエレガントな方法はありますか? 現在、k 最近傍の KDTree によって与えられる隣接行列を使用して、ブレス ファースト検索アルゴリズムを使用して接続されたコンポーネントを見つけますが、より良い可能性はありますか?

私

私は、C++ で OpenCV 3.1.0 を使用して、数字のスケルトンからの特徴抽出に取り組んでいます。スケルトン画像の閉じた輪郭の数を取得する方法を探しています (たとえば、8 の場合は 2、0,6,9 の場合は 1、1,2,3,4,5,7 の場合は 0)。connectedComponents()8 ウェイ接続で OpenCVの方法を使用しましたが、期待した結果が得られませんでした。すべての画像で常に2つの接続されたコンポーネントを取得します。問題は、形状の内側と外側が 8 方向に接続されているため、1 つのコンポーネントと見なされることです。

この画像は主な問題を説明します:

これらの機能を取得するソリューションはありますか?

MATLAB または C++ で最適化された 4 連結性または 8 連結性連結成分ラベリングのソース コードを探しています。MATLAB での連結成分ラベル付け (4 連結性) の多くの実装を見てきました。

より高速に動作する実装の 1 つは、ここで説明されている再帰的な実装です: http://www.mathworks.com/matlabcentral/fileexchange/38010-connected-component-labeling-like-bwlabel

MATLAB には、はるかに最適化された組み込みの bwlabeln または bwlabel があります。彼らは、Addison-Wesley の Sedgewick の Algorithms in C で説明されている 2 パス アルゴリズムの union-find メソッドを使用すると主張しています。ただし、そのソースコードを見つけるのは困難です。誰かがそれについて考えていますか？最適化されたコードが本当に必要です。

ユニオン検索アルゴリズムを使用して、無向グラフのすべての接続コンポーネントを検索しています。いくつかの不明な理由により、間違った答えが返されます。私が与える入力グラフは接続されていますが、そのグラフには 2 つの異なるラベルが出力されます。

誰かがこの異常を説明できれば幸いです。Union-Find が機能しない特別な無向グラフはありますか?

** グラフが少し大きいので、グラフを見やすくするために画像を追加しました。グラフをトリミングできませんでした。そうしないと、質問の本質が消えてしまいます。**

ここで、p と rk はそれぞれ親とランクです。

コード

ユニオン機能

検索機能

サンプル入力

グラフの写真

ノード 1、2、3、および 18 とそのエッジは考慮していないことに注意してください。

無向グラフ

私はSparkとGraphXを初めて使用し、接続されたコンポーネントを見つけるためにそのアルゴリズムでいくつかの実験を行いました。グラフの構造がパフォーマンスに強い影響を与えているように見えることに気付きました。

数百万の頂点とエッジを持つグラフを計算できましたが、グラフの特定のグループについて、アルゴリズムは時間内に終了せず、最終的にOutOfMemoryError: GC overhead limit exceeded.

このアルゴリズムは、長いパスを含むグラフに問題があるようです。たとえば、このグラフ{ (i,i+1) | i <- {1..200} }の場合、計算は失敗します。ただし、推移的なエッジを追加すると、計算はすぐに終了しました。

また、このようなグラフは問題ありませんでした:

問題を再現するための最小限の例を次に示します。

ファイルは次のinput.graphようになります (10 個のノード、それらを接続する 9 個のエッジ):

失敗するとハングしConnectedComponents.run(graph)ます。エラーメッセージは次のとおりです。

ローカルの Spark ノードを実行しており、次のオプションを使用して JVM を開始しています。

このおもちゃのグラフ (201 ノードと 200 エッジ) で問題が発生する理由を理解するのを手伝ってもらえますか? 一方、数百万のエッジを持つ現実的なグラフを約 80 秒で解決できますか? (どちらの例でも、同じセットアップと構成を使用しています。)

アップデート：

スパークシェルでも再現可能:

バグ レポートを作成しました: SPARK-15042

GraphX には、グラフの連結要素を見つけるためのアルゴリズムが付属しています。

それらの実装の複雑さについての声明は見つかりませんでした。

一般に、連結要素の検索は、幅優先検索や深さ優先検索などによって、線形時間で実行できます (ウィキペディアの記事を参照)。ただし、これはグラフをメモリに保持できることを前提としています。GraphX は分散型のアウト オブ コア アルゴリズムを実装しているため、比較することはできないと思います。

彼らのアルゴリズムがどのように機能し、どのような複雑さがあるか知っていますか?

matlabでは、使用できます

各連結成分のピクセル リストを取得します。pythonに相当するものは何ですか? 私は試した

ただし、ラベルを取得するために、これにはピクセル リストが付属していません。
助言がありますか？

私の目的は、R の 2 つの列間の共有値に基づいて、単一のデータ フレーム内の「接続された」行を識別することです。

この例では、10 個の一意のセグメント (つまり、データのクラスタ) があり、それぞれの一意のセグメントに対応する整数によって識別されます。各行は、互いに特定の距離のしきい値内にあると既に判断されている 2 つのセグメントを表します。列「segA」と「segB」の間に大きな違いはありません。これらは、接続されているセグメントのペアを追跡するためにのみ使用されます。列「距離」は、セグメントのペア間の距離を表しますが、データ フレームには「接続されている」と見なされるセグメントのペアのみが含まれているため、この時点では実際には必要ありません。

行間の接続セグメントを示す、「segA」または「segB」に少なくとも 1 つの共有値を持つすべての行を識別する方法を見つけようとしています。

私の最初の試みは、ループと論理ステートメントに対して複雑でした (R プログラミングは初めてです)。そのため、簡潔な解決策があれば大歓迎です!

例：

行 1 と 2 は、両方ともセグメント "1" を含むため、接続されています。

行 3 と 1 は、どちらもセグメント "2" を含むため、接続されています。

行 2 と行 3 は共有セグメントの存在によって直接接続されていませんが、行 1 を介した相互接続によって全体的に接続されています。

望ましい最終出力は次のようになります。

ここで、(1)、(2)、および (3) は、別個の全体セグメントと、直接/相互に接続されたそれらのコンポーネントを表します。

大きな配列に多数の異なるフォームがあり、と を使用して、numpyそれらの間の端から端までのユークリッド距離を計算したいと考えています。numpyscipy

注：検索を行いましたが、他の質問で尋ねられたように、ポイントまたは個別の配列間ではなく、配列内のラベル付きパッチ間の最小距離を取得したいため、これはスタックに関する以前の他の質問とは異なります。

私の現在のアプローチは KDTree を使用して機能しますが、大規模な配列に対しては恐ろしく非効率的です。基本的に、ラベル付けされた各コンポーネントの座標を調べて、他のすべてのコンポーネント間の距離を計算しています。最後に、例として平均最小距離を計算します。

Pythonを使用し、できれば追加のモジュールを使用しない、よりスマートなアプローチを探しています。

編集 @morningsunが提案したソリューションをテストしたところ、速度が大幅に向上しました。ただし、返される値はわずかに異なります。

編集2

あ、わかった。spatial.distance.pdist が適切な距離行列を返さないため、値が間違っていました。