3

四分木 (4 分木) を使用して、特定の BMP に情報を保持しようとしています。
BMP を指定してツリーを構築する方法を理解するのに苦労しています。

基本的に、すべての葉がピクセルを表すような構造になっています。各ノードには 4 つのポインターがあり、それぞれが画像内の残りの 4 つの象限の 1 つを指しています。したがって、各ノードは現在の画像を 4 つの部分に分割します。リーフに到達するまでに、1 つの特定のピクセルに到達します。

特定の画像をマッピングするためにツリーを構築する方法がわかりません。画像の次元が 2 のべき乗であると仮定すると、どうすればよいでしょうか。再帰関数がおそらくこれを最もエレガントに実行できることは理解していますが、画像のどこにいるのかを追跡する方法を理解するのに苦労しています。

これは C++ であり、現在私の quadtree.h ファイルには Node* ルートが含まれており、ノードはピクセル要素と他のノードへの 4 つのポインターを持つ構造として定義されています。各内部ノード (非リーフ ノード) は、それが導く 4 つの RGB 値すべての平均値を保持する必要があります。

アルゴリズムを作成しようとしていますが、.h ファイルに 1 つまたは 2 つの構造体を含める必要があると思います。この問題を解決するためのより良い/よりクリーンな方法はありますか?

4

2 に答える 2

2

ビットマップ データの保存方法によっては、やり方が異なる場合があります。ファイルから読み込んでツリーに直接ドロップしていますか? もしそうなら、.BMP ファイル (私の記憶が正しければ) は上部に幅と高さを示しているので、実際にそれを使用して、作成するレベルの数を正確に把握できます。

また、画像の大きさによっては、すべてのピクセルをノードの 2D 配列に格納し、ツリーを配列の「上に置く」ようにして、葉が配列にあり、他のすべてが他の場所にあるようにすることもできます。 . その場合、ネストされたループを記述して 4 つのノードのグループを取得し、それらの平均を計算してそれらをひとまとめにし、作成したばかりのノードで同じことを行うことができます。これは、ツリーを上から下に構築するよりもおそらく高速です。これは、4 ピクセルを超えて平均化することは決してないためです。一方、上から下に構築する場合は、最後のステップを除くすべてのステップで 4 ピクセルを超えて平均化する必要があります。

配列で実行したくない場合、私の考えでは、最も簡単な方法は、各ノードにその x、y 座標を追跡させることです。これにより、基本的に配列と同じことを行うことができますが、インデックスを差し込むだけではありません。

これは役に立ちましたか？ビットマップをどのように保存していますか? 最終目標は何ですか？

于 2010-06-01T14:03:06.480 に答える
1

STANN は、現時点で最高のオープン ソース実装です。

http://sites.google.com/a/compgeom.com/stann/

賢明なことに、ベルンらの四分木構築アルゴリズムを使用して、ファンキーなツリー操作をやめてください。

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.33.4634&rep=rep1&type=pdf

  1. すべてのポイントをモートン順に並べ替えます。
  2. 連続する点の各ペア間の四分木ボックスの長さを計算します。
  3. 親/兄弟を見つけるために、すべての最も近い最大値の計算を行います。

現在、OpenCl 用のライブラリを開発しています。テストが完了したら、リンクを投稿します。

于 2010-07-05T20:09:58.127 に答える