algorithm - 複数の画像をつなぎ合わせて 1 つの大きな画像にする

Question

複数の画像を 1 つの大きな画像にまとめようとしており、配置を最適に決定するアルゴリズムを探しています。画像を回転またはサイズ変更することはできませんが、結果の画像の位置は重要ではありません。

編集：サイズ変更制約を追加しませんでした

score 3 · Accepted Answer

3

おそらく、次のようなものを探しているでしょう: Automatic Magazine Layout。

于 2008-09-24T06:02:14.817 に答える

score 2 · Accepted Answer

どうやらそれは「パッキング問題」と呼ばれ、ゲームプログラミングでよく使われるものです。興味のある方のために、推奨される実装をいくつか示します。

ライトマップのパッキング、長方形のパッキング、および長方形の配置

score 0 · Accepted Answer

最適なパッキングは困難ですが、問題のドメインの詳細によっては単純化できる可能性があります。いくつかのアイデア:

ビットマップを同じサイズのタイルに分割できる場合、パッキングは簡単です。次に、必要に応じて、タイルからビットマップを再構築します。
画像を最大から最小に並べ替え、画像ごとに貪欲なアロケーターを使用して、画像に適合する最初の使用可能なサブ長方形を選択します。
遺伝的アルゴリズムを使用します。ランダムに選択されたいくつかのレイアウトから始めます。どれだけ密集しているかに基づいてスコアを付けます。スコアの高いものからソリューションを組み合わせて、許容できるスコアになるまで繰り返します。

score 0 · Accepted Answer

私はこのアルゴリズムを作成しました。これは実際にはNP-Hard Bin のパッキング問題の変形ですが、ビンのサイズは無限です。

それに関するいくつかの記事を見つけて、アルゴリズムを最適化しようとすることもできますが、最終的にはあらゆる可能性を試して、結果のビンサイズを最小化しようとする強引な方法のままです。

最善の解決策が必要ではなく、1 つの解決策だけが必要な場合は、すべての組み合わせをブルートフォーシングすることを避けることができます。私も一度それを行うプログラムを作成しました。

説明：

Images: array of the input images
ResultMap: 2d array of Booleans
FinalImage: large image

最大の画像が一番上になるように Images 配列を並べ替えます。
画像の合計サイズを計算し、そのサイズが画像の合計サイズの 1.5 倍になるように ResultMap を初期化します (メモリ使用量とパフォーマンスを向上させるために、この手順をよりスマートにすることができます)。ResultMap を同じサイズにし、False 値で埋めます。
次に、FinalImage の左側に最初の画像を追加し、ResultMap のすべてのブール値を 0,0 から ImageHeight、ImageWidth まで true に設定します。

ResultMap は、現在の FinalImage に画像を収めることができるかどうかをすばやく確認するために使用されます。int32 を使用し、各ビットを 1 ピクセルに使用するように最適化できます。これにより、(マスクを使用して) 32 ビットを一度にチェックできるため、メモリが削減され、パフォーマンスが向上します。ただし、画像のエッジを作成するために必要なマスクについて考える必要があるため、より困難になります。

Now I will describe the real loop of the "algorithm".

For each image in the array try to find a place were it would fit. You could write a loop which would look trough the ResultMap array and look for a false value and than start to see if it remains false in both directions for the size of the image to place.
- If you find a place, copy the image to the FinalImage and update the correct booleans in ResultMap
- If you cand find a place, increase the size of the FinalImage just enough (so look at the edges where the minimal amount of extra space is needed) and also sync that with the ResultMap
GOTO 1 :)

It's not optimal, but it can solve the problem in a reasonably optimal way (especially if there are a few smaller images to fill up the gabs in the end).