6

いくつかの制約付きで、画像を小さな画像に分割できるアルゴリズムを探しています。制約の 1 つは、空のピクセルを意味する「空白」を最小限に抑えることです。もう 1 つは、分割する画像の最大量を指定することです。

たとえば、下の画像を見てみましょう。その中にはたくさんの「空白」があります。この画像を他のいくつかの画像に分割して、この画像が占めるメモリの量を減らし、この画像が必要とする「描画」の量を減らしたいと思います。

.=transparent pixel
x=colored pixel

....................
.xxxxxxxxxxx........
...xxxx...xxxxxx....
.............xxxxx..
...............xxx..
...............xxx..
....................
..xxxxxx............
.....xxxxxxxxxxx....
.........xxxxxxxxxx.
....................

画像を最大4つの画像に分割したいとしましょう。可能な解決策は以下のようになります。

....................
.111111111111111....
.111111111111111....
.............22222..
.............22222.
.............22222..
....................
..3333333...........
..33333334444444444.
.........4444444444.
....................

誰かがこれのためのアルゴリズムを持っているか、これを行うアルゴリズムの名前を知っていますか? しばらく探していて、関連するアルゴリズムをいくつか見つけましたが、見つけたアルゴリズムは空白を考慮していません。たとえば、画像を非透明ピクセルのみをカバーする長方形に分割し、膨大な量の長方形になります。私が扱っている実際のデータは 1024*1024 ピクセルの画像であり、それらを最大 16 の部分に減らしたいと考えています。秘訣は、最小限の空白を使用して 16 個の画像を抽出することです。

4

5 に答える 5

2

私はravloonyと同じアルゴリズムを使用しますが、完全に空ではない最小/最大の列と行を探して残りを破棄する「クロップ」操作を使用して、わずかで重要な変更を加えます。

実際には、クロップ操作はX*Y入力として領域を取得し、4 つの整数 (領域で使用されているすべてのピクセルを含む最小の四角形の座標) を出力します。これは、空の領域を検出して破棄するためにも使用できます。

例

....................
.xxxxxxxxxxx........     xxxxxxxxxxx.......
...xxxx...xxxxxx....     ..xxxx...xxxxxx...
.............xxxxx..     ............xxxxx.
...............xxx.. =>  ..............xxx. (first crop)
...............xxx..     ..............xxx.
....................     ..................
..xxxxxx............     .xxxxxx...........
.....xxxxxxxxxxx....     ....xxxxxxxxxxx...
.........xxxxxxxxxx.     ........xxxxxxxxxx
....................

次に、画像を NxN の部分に分割し (ここでは N=4 を使用)、各部分でトリミング操作を使用します。

xxxxx|xxxxx|x....|
..xxx|x...x|xxxxx|
---------------------
     |     |  xxx|xx
     |     |  ..x|xx
---------------------
     |     |    x|xx
     |     |     |
---------------------
 xxxx|xx...|     |
 ...x|xxxxx|xxxxx|
     |...xx|xxxxx|xxx

この例では、わずか 34.2% の 21*11=231 ではなく、10+10+10+6+4+1+2+8+15+10+3=79 ピクセルが得られます。これは、手作りの 4 パーツ セグメンテーション (30+15+14+20=79) と同じ量になることに注意してください。

結論

もちろん、それぞれの 16 個のパーツの位置とサイズを追跡するための追加データがいくつかあり、常に最良の結果が得られるとは限りませんが、速度と節約の間の優れた妥協点であり、アルゴリズムは簡単に記述できます。と維持します。

追加データについて: サイズが 1024x1024 の画像を 4x4 の部分に分割すると、4 バイトの値を使用して各四角形を格納できるため、追加のデータ サイズは 16*4 = 64 バイトになります。これに関しては、おそらく考慮する必要があります。描画などの他の部分の速度が大幅に低下しない限り、最大 16 部分を増やします。

最悪の場合

このアルゴリズムの最悪のケースは、次のように、エッジ セットまたはその近くにいくつかのピクセルがあるパーツです。

x......x    xxxxxxxx    xx......
........    ........    x.......
........    ........    ........
x......x    ...x....    .......x

これらに対するいくつかの解決策が思い浮かびます。

  • 領域を再度分割します (四分木の実装になります)
  • 追加の手順を使用して、内部の完全に空の長方形を検出します。
  • パーツを定義するグリッドを少し翻訳する
于 2011-05-13T16:17:01.853 に答える
0

私の直感によると、理想的な解はナップザック問題に似ているため、計算上は非現実的です。ある種のヒューリスティックを使用して、「十分な」ソリューションを生成できる場合があります。

塗りつぶしアルゴリズムを使用して、不透明なピクセルの接続領域を選択できます。最初のカットとして、色のバラバラな領域ごとに長方形が得られます。予算内でより多くの長方形を利用できる場合は、さまざまな方法でそれらを切り取って、どの色のピクセルの「密度」が最も高くなるかを確認できます。

于 2011-05-13T16:34:47.030 に答える
0

必要なレベルに達するまで、半分または4つに分割するたびに再帰的に行うことを検討します（2 - > 4 ^ 2 = 16）。一番下のレベルで空の四角をチェックし、それらを破棄します。もちろん、これにより、最適に配置された四角形ではなく、元の画像の形状に比例した四角形のグリッドが得られますが、正しい方向に進む可能性があります。

于 2011-05-13T13:58:28.020 に答える
0

ランレングスまたはデルタ圧縮アルゴリズムを書きたい。または、スペース ファイリング カーブまたは空間インデックスを使用します。sfc は再帰的にサーフェスをより小さな 4 つのタイルに分割し、2 次元の複雑さを 1 次元に減らして、空白の識別を容易にします。Nick の hilbert-curve quadtree 空間インデックス ブログを探したいとします。私の php クラスのヒルベルト曲線を phpclasses.org からダウンロードしたいとします。

于 2011-05-13T13:23:03.167 に答える
0

コメントが遅くなって申し訳ありませんが、「良い」アルゴリズムを見つけるのに時間がかかりました。

いくつかの調査の後、私は次の解決策を探しています。まず、Quadtree を使用して SplitAndMerge を実行します。i 最初に「空白」で分割します。次に、すべての長方形を最大面積の長方形にマージしています。

その後、四分木を領域サイズでソートし、最大の x 領域のみを保持します。（したがって、本質的に最大の空白領域を維持します）。しかし、空白は必要ありません。空白以外のすべてが必要なので、Quadtree を反転し、SplitAndMerge を再度実行します。次に、画像から残りの四角形を抽出し、それらを最終的な画像にビンパッキングします。

これにより、いくつかの優れた結果が得られ、画像サイズが大幅に縮小され (画像に多くの空白が含まれていたため)、それらを描画する時間を最小限に抑えることができました。

于 2011-05-23T20:49:11.187 に答える