5

デジタル形状は、バイナリ イメージ (ブロブ) 内の一連の接続されたピクセルです。

これは、ランレングス コーディングによってコンパクトに表すことができます。つまり、ピクセルを水平線分にグループ化し、始点の座標と長さを格納します。通常、RLC 表現はランをラスター順に格納します。つまり、行ごとに右に並べます。

滑らかな形状の場合、ストレージ要件は O(N²) から O(N) に低下します。

形状の輪郭は、(塗りつぶしアルゴリズムによって) 内部が塗りつぶされたときに形状を復元する、ピクセルの閉じたチェーンです。これは O(N) 表現でもあります。形状がビットマップとして利用できる場合、アウトラインは輪郭アルゴリズムによって取得できます。

中間ビットマップに描画せずに、RLC 表現を指定して形状の輪郭を直接計算するアルゴリズムを探しています。アルゴリズムは、実行回数に比例して時間内に実行されることが期待されます。

ここに画像の説明を入力

あなたは解決策に出くわしましたか？

4

3 に答える 3

1

塗りつぶされているが、塗りつぶされていないピクセルに隣接している場合、そのピクセルは境界ピクセルです。塗りつぶされたピクセルの行ごとの RLE エンコードが与えられた場合、隣接する 3 つの行を操作して、境界ピクセルの RLE バージョンを計算し、それをデコードできます。

基本的に、スイープ ライン アルゴリズムがあります。のような3行で

   ***********   ****
************************
  ****        ******

^RLE からイベント ポイント ( ) を取得します。

   ***********   ****
************************
  ****        ******
^ ^^  ^       ^  ^  ^^  ^

最初に行うことは、上または下に空のピクセルがある中間の塗りつぶされたピクセルを境界として指定することです。(ガイダンスが必要な場合は、間隔のリストの集合差のアルゴリズムは非常に似ています。)

   ***********   ****
BBB***BBBBBBBBBBB***BBBB
  ****        ******

次に、塗りつぶされているが境界であることがわかっていない間隔について、左端点の左側にスペースがあるかどうか、および右端点の右側にスペースがあるかどうかを確認します。もしそうなら（それぞれ）、それらは境界です。

于 2015-09-02T14:18:39.803 に答える
0

注：この回答は、「非アウトライン」が「4つの隣人に囲まれている」ことを意味すると想定しているため、結果は例とは少し異なります（青ではなく緑が1ピクセル）。

すべてのアウトライン ピクセルは、4 つの「隣接ピクセル」(ピクセルの左、右、上、下) のすべてが設定されていないピクセルです。

RLC を上から下にデコードすると、次の疑似コード アルゴリズムを使用してアウトライン ピクセルを取得できます。

 For the first line
   All decoded pixels are outline pixels
 For the subsequent lines
   Leftmost and rightmost pixels of each RLC run are outline pixels
   All other pixels are outline pixels if:
     The pixel above isn't set (case A)
     The pixel below isn't set (case B)

ケース A と B は、現在のピクセルの上/下のピクセルを調べる必要があることを意味します。そのため、アルゴリズムは実際には一種のパイプライン化されているか、1 行先を見ている必要があります。ケース B は次の行まで検出できないためです。デコードされました。

編集:後でピクセルを時計回りに並べ替えるには、アウトラインが斜めに接続された 1 ピクセル幅の線であるという事実を使用できます。一番上の行のピクセルの 1 つを選択すると、現在のピクセルの右、下、または真下にあるピクセルに続いて、次の 2 つのピクセルが可能になります。その後、隣接ピクセルがなくなるまで、まだ訪れていない隣接ピクセルをたどります。例：

  /----- First pixel you pick, A and B are neighbour candidates, A is the "correct" one
  v
  xAxxx           
 B     x        
 x    x      xxx
 x     xxxxxx   x
  xx           x
    xxxxxxxxxxx

  s0123             Result after following the neighbours (s = start, e = end),
 e     4            numbers from 0-9 show order of traversal
 1    5      234
 0     678901   5
  98           6
    76543210987
于 2015-09-02T14:19:55.790 に答える
0

ヒント:

他の回答で述べたように、アウトライン ピクセルのリストを出力することは、実行エンドポイントの 3x3 近傍が検査されるスイープライン プロセスとして実装できます。

この手順では、保存して並べ替える必要がある一連の直接アークと逆アークとして、スクランブルされた方法でピクセルを放出します。

別の方法として、希望する順序でアウトライン ピクセルを列挙する利点を持つ標準の Moore Neighborhood アルゴリズムを実装するというアイデアに基づくものがあります。

この手順では、現在のピクセルの周囲の 8 つの近傍構成を知る必要があります。この考え方は、別のピクセルに移動するたびにこの近傍を更新することです。現在のピクセルを含むランと、行内の 2 つの向かい合ったランへのインデックスを維持します。上と下。

別のピクセルに移動するたびに、これら 3 つのインデックスを更新する必要があります。これには、並べ替えられたランのリストでの短い順次検索が含まれます。これは、ピクセルへの疑似ランダム アクセス メカニズムと見なすことができます。これは、連続するアクセスが非常にローカルであり、一種のキャッシュが可能であることを考慮に入れることができます。

更新：

私が使用するランレングス コード表現では、黒いランのみがトリプルとしてコード化され(X, Y, L)ます。実行は行ごとに上から下に並べ替えられ、次に左から右に並べられます。

便宜上、すべての画像行が次々に追加され、すべてのピクセルが 1 つの数値Z = X + Y.Nx(Nxは画像の幅) で指定されているかのように、"リニア アドレス指定" スキームに切り替えることができます。

したがって、黒のランのリストがあり、白のランは 2 つの連続する黒のランの間に暗黙的に検出されます。

処理中、現在のピクセルの直前またはそのピクセルで始まるランのインデックスを常に覚えておくことができます ( R[I].Z <= Z < R[I+1].Z)。ランの内側にいるか、ランと次の間にあるかを確認することで、ピクセルの色を知ることができます ( Z < R[I].Z + R[I].L)。

位置を 1 つ左に移動すると、Zが減少し1、前の実行を選択する必要がある場合があります ( I--)。

1 ポジション上に移動すると、Z減少しNx、数回の実行でバックトラックする必要がある場合があります (再び実行さI--れるまでR[I].Z <= Z)。

ここに画像の説明を入力

この図は、現在のピクセルとその 4 つの隣接ピクセル、および黒ランの「影響ゾーン」を示しています。8 つの変位方向すべてを同様に処理できます。

ご覧のとおり、すべての移動は、小さな値と見なされる、連続した実行の数に等しい悪い操作を必要とします。この概念を使用すると、ビットマップ全体を再構築することなく、妥当なコストで任意のパスに従って RLC 表現をトラバースできます。

Moore Neighborhood アルゴリズムは、アウトラインの長さに線形に時間がかかるため、この線形実行アドレス指定に基づく実装も線形時間になります (行ごとの実行数が制限されている場合)。

于 2015-09-02T15:26:21.097 に答える