c++ - 8 連結ピクセルのリストからセグメントを抽出する

Question

現在の状況: 画像からセグメントを抽出しようとしています。openCV のメソッドのおかげfindContours()で、すべての等高線の 8 連結点のリストができました。ただし、これらのリストには多くの重複が含まれているため、直接使用することはできません。

問題:重複を含む可能性のある 8 連結点のリストを指定して、そこからセグメントを抽出します。

可能な解決策：

• 最初はopenCVのapproxPolyDP()方法を使いました。ただし、結果はかなり悪いです...ズームされた等高線は次のとおりです。

の結果は次のとおりですapproxPolyDP(): (9 セグメント! 一部重複)

しかし、私が欲しいのはもっと似ています:

approxPolyDP()「いくつかのセグメントに見える」ものを「いくつかのセグメント」に変換できるので悪いです。ただし、私が持っているのは、それ自体を数回反復する傾向があるポイントのリストです。

たとえば、私のポイントが次の場合：

0 1 2 3 4 5 6 7 8 
  9   

次に、ポイントのリストは次のようになります0 1 2 3 4 5 6 7 8 7 6 5 4 3 2 1 9...そして、ポイントの数が大きくなった場合（> 100）、によって抽出されたセグメントapproxPolyDP()は残念ながら重複していません（つまり、互いに重なり合っていますが、厳密には等しくないので、できます'たとえば、ピクセルとは対照的に、「重複を削除する」と言うだけです）

• おそらく、私は解決策を持っていますが、それはかなり長いです (興味深いですが)。まず、すべての 8 連結リストに対して、疎行列を作成し(効率化のため)、ピクセルがリストに属している場合は行列の値を 1 に設定します。次に、ピクセルに対応するノードと隣接するピクセル間のエッジを持つグラフを作成します。これは、ピクセル間に欠けているすべてのエッジを追加することも意味します(複雑さが小さいため、スパース マトリックスが原因である可能性があります)。次に、可能なすべての「正方形」 (隣接する 4 つのノード) を削除します。これは、すでにかなり細い輪郭で作業しているため可能です。次に、最小スパニング ツリーアルゴリズムを起動します。そして最後に、ツリーのすべてのブランチを openCV で近似することができますapproxPolyDP()

要約すると、エラーが発生しやすいように思われるため、まだ実装していない面倒な方法があります。ただし、スタック オーバーフローの皆さんにお尋ねします。他に既存のメソッドがあり、適切に実装されている可能性がありますか?

---

編集：明確にするために、ツリーを作成したら、「ブランチ」を抽出できます（ブランチは、3つ以上の他のノードにリンクされた葉またはノードから始まります）次に、openCVのアルゴリズムapproxPolyDP()はRamer–Douglas–Peuckerアルゴリズムです。それが何をするかのウィキペディアの写真：

この図では、ポイントが互いに重複している可能性がある場合に失敗する理由を簡単に理解できます

---

別の編集: 私の方法では、注目すべき興味深いことがあります。グリッド内に配置されたポイント (ピクセルなど) を考慮する場合、一般に、最小スパニング ツリー アルゴリズムは有用ではありません。

X-X-X-X
|
X-X-X-X

とは根本的に大きく異なります。

X-X-X-X
| | | |
X X X X

しかし、どちらも最小全域木です

ただし、私の場合、ノードは輪郭であると想定されているため、ノードがクラスターを形成することはめったにありませんfindContours()。

---

トマラクのコメントへの回答：

DP アルゴリズムが 4 つのセグメントを返す場合 (点2から中心までのセグメントが 2 回ある)、私は満足です! もちろん、適切なパラメータを使用すると、「たまたま」同一のセグメントが存在する状態になり、重複を削除できます。ただし、明らかに、アルゴリズムはそのように設計されていません。

以下は、セグメントが多すぎる実際の例です。

Answer 1

Mathematica 8 を使用して、画像内の白いピクセルのリストから形態グラフを作成しました。最初の画像で問題なく動作しています:

形態グラフを作成します。

graph = MorphologicalGraph[binaryimage];

次に、関心のあるグラフ プロパティをクエリできます。

これにより、グラフの頂点の名前が得られます。

vertex = VertexList[graph]

エッジのリスト:

EdgeList[graph]

そして、それは頂点の位置を与えます:

pos = PropertyValue[{graph, #}, VertexCoordinates] & /@ vertex

最初の画像の結果は次のようになります。

In[21]:= vertex = VertexList[graph]

Out[21]= {1, 3, 2, 4, 5, 6, 7, 9, 8, 10}

In[22]:= EdgeList[graph]

Out[22]= {1 \[UndirectedEdge] 3, 2 \[UndirectedEdge] 4,  3 \[UndirectedEdge] 4, 
          3 \[UndirectedEdge] 5, 4 \[UndirectedEdge] 6,  6 \[UndirectedEdge] 7, 
          6 \[UndirectedEdge] 9, 8 \[UndirectedEdge] 9,  9 \[UndirectedEdge] 10}

In[26]:= pos = PropertyValue[{graph, #}, VertexCoordinates] & /@ vertex

Out[26]= {{54.5, 191.5}, {98.5, 149.5},  {42.5, 185.5}, 
          {91.5, 138.5}, {132.5, 119.5}, {157.5, 72.5},
          {168.5, 65.5}, {125.5, 52.5},  {114.5, 53.5}, 
          {120.5, 29.5}}

ドキュメンテーションhttp://reference.wolfram.com/mathematica/ref/MorphologicalGraph.htmlを考えると、コマンド MorphologicalGraph は最初にモルフォロジー間引きによってスケルトンを計算します。

skeleton = Thinning[binaryimage, Method -> "Morphological"]

次に頂点が検出されます。それらは分岐点と終点です。

verteximage = ImageAdd[
                  MorphologicalTransform[skeleton, "SkeletonEndPoints"],   
                  MorphologicalTransform[skeleton, "SkeletonBranchPoints"]]

そして、それらの接続性を分析した後、頂点がリンクされます。

たとえば、頂点の周りの構造を壊すことから始めて、接続されたコンポーネントを探し、グラフのエッジを明らかにすることができます。

comp = MorphologicalComponents[
           ImageSubtract[
               skeleton, 
               Dilation[vertices, CrossMatrix[1]]]];
Colorize[comp] 

悪魔は細部に宿りますが、独自の実装を開発したい場合、それは確かな出発点のように思えます。

Answer 2

数学形態学を試してください。まず、穴を埋めるために画像を作成する必要がありdilateます。close

cvDilate(pimg, pimg, NULL, 3);
cvErode(pimg, pimg, NULL);

私はこの画像を手に入れました

次のステップでは、間引きアルゴリズムを適用する必要があります。残念ながら、これは実装されていませんOpenCV(MATLAB にはbwmorphwiththin引数があります)。たとえば、MATLAB を使用して、画像を次のように調整しました。

ただし、OpenCV間引きを実装するために必要な基本的なモルフォロジー操作はすべてあります ( cvMorphologyEx、cvCreateStructuringElementExなど)。

別のアイデア。

彼らは、距離変換はそのようなタスクに非常に役立つようだと言います. そうかもしれません。機能を考慮cvDistTransformします。次のようなイメージを作成します。

次に、次のようなものを使用しますcvAdaptiveThreshold。

それが骨格です。接続されているすべての白いピクセルを反復処理し、曲線を見つけて小さなセグメントを除外できると思います。

Answer 3

以前に同様のアルゴリズムを実装したことがあり、一種の増分最小二乗法で実装しました。それはかなりうまくいった。擬似コードは次のようになります。

L = empty set of line segments
for each white pixel p
  line = new line containing only p
  C = empty set of points
  P = set of all neighboring pixels of p
  while P is not empty
    n = first point in P
    add n to C
    remove n from P
    line' = line with n added to it
    perform a least squares fit of line'
    if MSE(line) < max_mse and d(line, n) < max_distance
      line = line'
      add all neighbors of n that are not in C to P
  if size(line) > min_num_points
    add line to L

ここで、MSE(線) は線の平均二乗誤差 (最適な線までの二乗距離の線内のすべての点の合計) であり、d(線、n) は点 n から線までの距離です。max_distance の適切な値はピクセル程度のようで、max_mse はそれよりもはるかに小さいようで、画像の線分の平均サイズに依存します。私にとっては、0.1 または 0.2 ピクセルがかなり大きな画像で機能しました。

私は Canny オペレーターで前処理された実際の画像でこれを使用していたので、私が得た唯一の結果はそれです。画像に対する上記のアルゴリズムの結果は次のとおりです。

アルゴリズムを高速にすることも可能です。私が持っている C++ 実装 (私の仕事によって強制されたクローズド ソース、申し訳ありませんが、そうでなければ私はあなたにそれを与えるでしょう) は、約 20 ミリ秒で上記の画像を処理しました。これには、エッジ検出のための Canny 演算子の適用が含まれているため、この場合はさらに高速になるはずです。