4

さまざまなテキストや図形が描かれた白黒の画像がたくさんあります。私の目標は、各画像を黒い領域を囲むポリゴンのセット (頂点のセットとして定義) に変換することです (魔法の杖ツールが写真編集ソフトウェアで領域を選択できるのと同じ方法で)。

私はこれを JavaScript で実装することを好みますが、これをどのように行うかという概念に最も関心があります。ありがとう！

4

3 に答える 3

1

周囲のみをスキャンする必要がある場合は、「右手を壁に当てる」アルゴリズムを作成できます。

ステップ 1: 画像を右に移動して、反対色の最初のピクセルを見つけます。
ステップ 2: 現在のピクセルのすべての隣接ピクセルを時計回りに検索します。
ステップ 3: 最初の使用可能なピクセルに移動します。ピクセル インデックスを保存し
ます。 ステップ 4: 現在のピクセルがステップ 1 の開始ピクセルになるまで、ステップ 2 ～ 3 を繰り返します。

ステップ 5: 格納されたピクセルからパターンを検出します。たとえば
、LLLLLLLLLL の実行、[左] 上、右、または下、

形のパターン

RRRRRRR U RRRRRRR U RRRRRRRR U RRRRRRR U ...
<-N--->   <--N-->   <--N+1->   <--N-->

線でモデル化できますが、線分の可能な限り最良の開始点と終了点を検出するために「逆ブレゼンハム」を実行するのはそれほど簡単ではありません。

いずれにせよ、ブルート フォース アプローチを使用して、現在のピクセルから N 個の前のピクセルまで線を引き、ブレゼンハム アルゴリズムがまったく同じピクセルを生成するかどうかをテストできます。

于 2012-10-31T10:26:55.203 に答える
1

簡単なビットマップ エディターで魔法の杖が機能する方法は次のとおりです。

選択した元の点の色を色 C とします。最後の色 LC を任意の色とします。

  1. 選択した点 (x,y) を取得
  2. (x,y) の色 = C で、ピクセルがアクセスされていない場合
    1. 座標を配列に格納する
    2. (x+1,y)、(x-1,y)、(x,y+1)、(x,y-1) の繰り返しアルゴリズム
  3. 訪問したピクセルの配列にピクセルを格納する
  4. (x,y) の色 != LC の場合
    1. ピクセルを配列内の境界ピクセルとしてマークする
    2. LC = (x,y) の色を設定します。
于 2012-10-31T09:40:16.243 に答える
0

まず、「エッジ」とは何かを説明します。

エッジは、隣接する 2 つのピクセル間の仮想線です。

+---+---+
| A | B |  // The middle line is the edge between pixel A and pixel B
+---+---+

エッジには始点と終点があり、上向き、下向き、「左向き」または「右向き」です。

画像の境界を横切るポリゴンを処理するために、画像の周りに 1 ピクセルの白い境界線を追加します。

アルゴリズムは次のとおりです。

For each row of our image {  
  For each pixel of the row except the last one {  
    If current pixel is white and next pixel is black {
      Create a new upward edge between the two pixels and add it to
      the global edge list.
    }
    Else if current pixel is black and next pixel is white {
      Create a new downward edge between the two pixels and add it to
      the global edge list.
    }
  }  
}
For each column of our image {  
  For each pixel of the column except the last one {  
    If current pixel is white and next pixel is black {
      Create a new "left going" edge between the two pixels and add it to
      the global edge list.
    }
    Else if current pixel is black and next pixel is white {
      Create a new "right going" edge between the two pixels and add it to
      the global edge list.
    }
  }  
}  

For each edge of the global edge list {
  Find the edge starting from the point where your current edge ends
  (for now on, we gonna call it next_edge).
  Connect the two edges to form a linked list
  (edge->next = next_edge; next_edge->previous = edge;)
}

While there is edges in the global edge list {
  Create a new polygon and add it to the polygon list
  Take the first edge of the list (for now on, we gonna call it first_edge)
  For each edge in the linked list starting at first_edge {
     Remove edge from global edge list
     Add edge to polygon's edge list
  }
}

ポリゴンのリストができました。

編集

もちろん、使用する前に少し最適化する必要がありますが、それは非常に簡単です。同じ向きの連続したエッジを単一の長いエッジに置き換えることができます。

于 2012-10-31T10:26:23.237 に答える