6

I've read so many articles, but none seem to answer this question. Or maybe I'm just not understanding. I'm attempting to build a quadtree so that it can represent an image. The leaf nodes are to hold pixels, and non-leaf nodes will hold the average value pixel of its children.

My question is:

How does it work that the leaf nodes only hold pixels? Why don't the other nodes hold pixels? And how do we know how many times to subdivide our original root node to represent that given image? Do we just subdivide it n times, where n is the height and width (for a square)?

Edit: So how do I keep track of leaf nodes, so I know when to add pixels at that location? Right now I have a helper function that divides the regions for me, keeping track of width and height.

4

4 に答える 4

6

四分木は、サイズが2の累乗である正方形の画像（たとえば、ほとんどのテクスチャ）に最適です。各ノードを「ピクセル」を表すものと考えるべきではありません。代わりに、「サイズ2^kのピクセルの正方形のブロック」を表すと考えてください。最終的な葉の場合、kは0であるため、各葉のノードは、サイズ1のピクセルの正方形のブロック、つまり1つのピクセルを表します。ツリーの内部ノードは、画像のますます大きなセクションを表します。

于 2011-03-16T01:58:22.360 に答える
1

なぜリーフノードだけがピクセルを保持するのですか？非リーフノードがピクセルを保持しているかどうかを自問してみてください。その場合、その子は何を保持しますか？ピクセルを細分化することはできないので、答えは明らかに何もありません。そのようなノードはあり得ません。

何回細分化するかをどうやって知るのですか？もちろん、四分木を構築する理由に応じて、それを行うには複数の方法があります。一般に、エントロピーが大きい（「詳細」が多い）画像の領域はより細かく分割する必要がありますが、エントロピーが低く「平坦な」領域は分割を少なくすることができます。いつどこで細分化するかを選択するためのさまざまなアルゴリズムがあります。一般に、領域内のピクセル値を比較し、差がしきい値を超えると分割されます。

于 2011-03-16T01:55:00.443 に答える
0

リーフノードがピクセルのみを保持することはどのように機能しますか？他のノードがピクセルを保持しないのはなぜですか？

これは、Quadtreeを何に使用しているかによって異なります。あらゆる種類の情報を他のノードにリンクできます。左上隅へのポインターと、このノードが表す長方形の幅/高さですが、ほとんどの場合は必要ありません（または平均的なものが必要です）。物事をスピードアップするために事前計算できる値）。

そして、その与えられた画像を表すために元のルートノードを何回細分化するかをどうやって知るのでしょうか？

細分化するたびに、領域の幅と高さの半分になるため、サイズの正方形の画像の場合は時間nを細分化する必要がありlog2(n)、サイズの非正方形の画像のn*m場合はほとんどのステップが必要になりmax(log2(n), log2(m))ます。

于 2011-03-16T01:53:44.473 に答える
0

あなたの質問に答える最良の方法は、あなたが尋ねなかった2つの質問に答えることだと思います。

  • 四分木とは何ですか？
  • これを不規則な密度のモデリングシステムにどのように適用できますか？

四分木は、2次元の二分木です。そのため、リーフ以外のノードごとに（最大）4つの子があります。これにより、データベースがバイナリツリーまたはそのバリエーションを使用して単一の次元にインデックスを付けるのと同じように、平面にインデックスを適用できます。同じ非常に有利なスパース位相空間表現プロパティを使用します。

これを画像圧縮とプログレッシブ表示に適用することは非常に明白です。深さnに制限されたツリーウォークを実行すると、画像空間全体にまたがる4^n個の画像情報が得られます。1レベル深くすると、各ピクセルは4つに分割されます。正しく思い出せば、JPEG2000はこのように動作します。「画像情報の項目」と言ったのは、1ビットである必要がないからです。アイテムは、32ビットARGBまたはその時点でのスペースを説明するその他のプロパティ（または複数のプロパティ）である可能性があります。

于 2011-06-04T14:04:07.610 に答える