クアッドツリー: 画像解析のための階層データ構造の探索

By Fouad Sabry

クアッドツリーとは

クアッドツリーは、各内部ノードがちょうど 4 つの子を持つツリー データ構造です。 クオッドツリーはオクツリーの 2 次元類似物であり、2 次元空間を 4 つの象限または領域に再帰的に細分することによって分割するために最もよく使用されます。 リーフ セルに関連付けられたデータはアプリケーションによって異なりますが、リーフ セルは「興味深い空間情報の単位」を表します。

どのようなメリットがあるか

(I) 次のトピックに関する洞察と検証:

第 1 章: クアッドツリー

第 2 章: オクツリー

第 3 章: R ツリー

第 4 章: バイナリ ツリー

第 5 章: B ツリー

第 6 章: AVL ツリー

第 7 章: 赤黒の木

第 8 章: 二分探索ツリー

第 9 章: バイナリ ヒープ

第 10 章: セグメント ツリー

(II) クアッドツリーに関する一般のよくある質問に答える。

(III) 多くの分野でのクアッドツリーの使用例。

この本の対象者

専門家、学部生、大学院生、愛好家、愛好家、およびあらゆる種類の Quadtree に関する基本的な知識や情報を超えたいと考えている人。

 

• Language: 日本語
• Publisher: 10億人の知識があります [Japanese]
• Release date: May 14, 2024

Book preview

第1章:クワッドツリー

四分木のデータ構造は、各内部ノードにちょうど 4 つの子孫がある木です。四分木は八分木に相当する 2 次元であり、通常、2 次元空間を 4 つの象限またはセクションに分割するために使用されます。リーフセルに紐づく情報は用途によって異なりますが、リーフセルは「興味深い空間情報の単位」です。

分割されたゾーンは、任意の形状、正方形、または長方形の形状を持つことができます。1974年、Raphael FinkelとJ.L. Bentleyによってこのデータ構造がクワッドツリーに指定されました。Qツリーは、同様のパーティションスキームの別の用語です。すべてのタイプのクワッドツリーには特定の特性があります。

それらは空間を柔軟なセルに分解します。

各コンパートメント(またはレセプタクル)には最大容量があります。バケットの最大容量に達すると、バケットは分離します。

ツリーディレクトリは、四分木の空間分解に準拠します。

ツリーピラミッド(Tピラミッド)は「完全な」ツリーです。T ピラミッドのすべてのノードには、リーフ ノードを除く 4 つの子ノードが含まれています。すべての葉は同じレベルにあり、画像内の個々のピクセルに対応します。完全な二分木を配列にコンパクトに格納する方法と同様に、ツリーピラミッドデータは暗黙のデータ構造として配列にコンパクトに格納できます。

クワッドツリーは、面積、点、線、曲線など、四角形が表すデータのタイプに基づいて分類できます。四角形木は、木の形状が処理順序に依存しないかどうかに基づいて分類することもできます。その後は、クワッドツリーの頻繁な形式です。

領域四分木は、領域を 4 つの等しい象限、サブ象限などに分解することによって空間の 2 次元分割を示し、各リーフ ノードは特定のサブ領域に関連するデータを運びます。ツリー内の各ノードには、正確に 4 つの子があるか、まったくない (リーフ ノード) かのどちらかです。この分解方法(つまり、より細分化が求められるサブ象限に関連データがある限り、サブ象限を細分化)により、四分木の高さは、分解される空間内の興味深い領域の空間分布に敏感になり、依存します。領域四分木は、トライデータ構造の変形です。

深さがnの領域四分木は、2n×2nピクセルからなる画像を表すために使用され得、ここで、各ピクセルは0または1のいずれかである。

ルート ノードは、イメージ領域の全体を表します。

いずれかの領域内のピクセルが完全に0または1でない場合、その領域は無効と見なされ、セグメント化されます。

これはアプリケーションであり、各リーフ ノードは、完全に 0 または 1 で構成されるピクセルのブロックを表します。

これらのツリーを画像ストレージに利用した場合に、スペースを節約できる可能性があることに注意してください。視覚描写に共通する特徴は、全体に同じ色値を持つ大きな領域が多数あることです。

画像内のすべてのピクセルの大きな 2 次元配列を格納する代わりに、より小さな配列が使用されます。 四分木は、ピクセル解像度サイズのセルよりも多くの分割レベルで同じ情報をキャプチャできます。

ツリーの解像度とサイズは、ピクセルと画像のサイズによって制限されます。

領域四分木は、変更可能な解像度でデータフィールドを表すためにも使用できます。たとえば、四角木を使用して領域内の温度を記録し、各リーフ ノードが表すサブ領域の平均温度を格納できます。

点のクワッドツリー

以下は、ポイント クワッドツリーの構築方法です。次に挿入するポイントを指定すると、対応するセルが検索され、そのポイントがツリーに追加されます。新しいポイントが挿入され、そのポイントを含むセルは、そのポイントを通る垂直線と水平線によって四分円に分割されます。したがって、セルは長方形ですが、常に正方形であるとは限りません。これらのツリーの各ノードは、入力ポイントの 1 つを保持します。

平面のパーティションは点の挿入順序によって決定されるため、ツリーの高さは敏感であり、挿入順序に依存します。「間違った」順序で挿入すると、入力ポイントの数に比例した高さのツリーが作成される可能性があります(その時点でリンクリストになります)。前処理を使用すると、ポイント セットが静的な場合に、バランスの取れた高さのツリーを生成できます。

点四分木のノードは二分木のノードに似ていますが、主な違いは、従来の二分木のように2つ(「左」と「右」)ではなく、4つのポインタ(各象限に1つ)があることです。さらに、キーは通常、x 座標と y 座標を参照する 2 つのコンポーネントに分割されます。その結果、ノードには次のデータが含まれます。

4 つのポインター: quad['NW']、quad['NE']、quad['SW']、および quad['SE']

点;これには、次のものが含まれます。

識別子;通常、X、Y座標で表されます

値 (名前など)

ポイント領域 (PR) クワッドツリーは、リージョン クワッドツリーに非常によく似ています。違いは、保存されるセル関連データの種類にあります。領域四分木では、リーフ セルの領域全体に適用される値が保持されます。ただし、PR クワッドツリーのセルには、リーフ セル内に存在するポイントのリストが保持されます。前述したように、この分解アプローチを採用した樹木の高さは、ポイントの空間分布に依存します。ポイント クワッドツリーと同様に、PR クワッドツリーは、「不適切な」セットが指定されている場合、線形の高さを持つ場合があります。

エッジ クワッドツリー (PM クワッドツリーに類似) は、ポイントとは対照的にラインを保持するために使用されます。セルは、曲線を近似するために、セルごとに 1 つの線分ができるまで正確に、非常に細かい解像度に細分化されます。エッジのクワッドツリーは、コーナー/頂点付近で最大分解レベルに達するまで分割を続けます。これにより、ツリーのバランスが著しく崩れ、インデックス作成の目標が無効になる可能性があります。

ポリゴン マップ クワッドツリー (または PM クワッドツリー) は、縮退する可能性のあるポリゴンのグループを保持するために使用されるクワッドツリーのバリアントです (つまり、孤立した頂点またはエッジを持つポリゴン)。PM クワッドツリーとエッジ クワッドツリーの大きな違いは、セル内のセグメントが頂点で交差する場合、調査対象のセルが分割されないことです。

PM クワッドツリーには主に 3 つの種類があり、各ブラック ノードに格納されているデータによって異なります。PM3 クワッドツリーは、交差しないエッジを任意の数、最大で 1 つのポイントを保持できます。PM2 クワッドツリーは PM3 クワッドツリーと同じですが、すべてのエッジが同じ位置で終端する必要がある点が異なります。PM1 クワッドツリーは PM2 クワッドツリーと似ていますが、黒色のノードにはポイントとそのエッジ、またはポイントを共有するエッジのセットのみを含めることができますが、ポイントとポイントを含まないエッジのセットは許可されません。

このセクションでは、Sariel Har-bookの章を要約します。ペレドの。

細分化されたセルに対応するすべてのノードを格納すると、ストレージの必要性が法外になり、かなりの数の空のノードを格納することになります。

これらのまばらな木のサイズを小さくするには、葉に興味深いデータが含まれているサブツリーのみを保存する必要があります(つまり、

「重要なサブブランチ」)。

実際には、サイズをはるかに小さくすることができます。

本質的なサブツリーだけを保持する場合、剪定の手順により、次数2の中間ノード(1つの親と1つの子へのリンク)を持つツリーに長いルートが残る可能性があります。

このパスの先頭にノードを格納 u し(そして、削除されたノードを表すためにメタデータを関連付け)、その末尾をルートとするサブツリーをにアタッチするだけでよいことがわかりました u 。

「貧弱な」入力ポイントが与えられた場合、これらの圧縮されたツリーは線形の高さを持つ可能性があります。

この圧縮中にかなりの量のツリーが刈り込まれますが、Zオーダー曲線を使用して対数時間検索、挿入、削除が可能です。

Z オーダー曲線は、完全な四分木 (したがって、圧縮された四分木) の各セルを O(1) 時間的に 1 次元の線にマッピングし (また、時間内にもマッピング O(1) し)、要素の完全な順序を確立します。

したがって、四分木を順序集合データ構造(ツリーのノードを格納する)に格納できます。

続行する前に、妥当な仮定を述べる必要があります: {\displaystyle \alpha ,\beta \in [0,1)} 2進数として表現された2つの実数が与えられた場合、 O(1) それらが異なる最初のビットのインデックスを時間内に計算できると仮定します。

また、 O(1) クワッドツリー内の 2 つの点/セルの最小の共通祖先を時間内に計算し、それらの相対的な Z オーダーを確立し、フロア関数を時間的に計算できると仮定します O(1) 。

これらの前提では、特定のポイントのポイント位置 q (つまり、

を含むセルの決定 q )、挿入、および削除操作はすべて時間内に実行できます O(\log {n}) (つまり、

基になる順序セットデータ構造内で検索を実行するのに必要な時間)。

ポイント位置( q つまり、

圧縮されたツリーで対応するセルを見つけます)。

圧縮されたツリーで、Z オーダーで前にある既存のセルを検索します q 。

このセルを と呼ぶ v 。

の場合は {\displaystyle q\in v} 、 を返します v 。

そうでない場合は、非圧縮四分木のポイント q とセル v の最下位の共通祖先を見つけます。

これを祖先セル と呼ぶ u 。

圧縮されたツリーで、Z オーダーで前にある既存のセルを検索し u 、それを返します。

詳細は省きますが、挿入・削除は、挿入・削除したい項目の点配置を先に行い、次に挿入・削除します。必要に応じて、ノードを追加または削除してツリーの形状を変更するように注意する必要があります。

画像表現

Bitmap and its compressed quadtree representation

画像処理

メッシュ生成

空間インデックス、ポイントベース、範囲ベースの検索

2次元衝突検出効率

地形のデータ錐台カリングを表示する

疎なデータストレージ (スプレッドシートや行列計算の形式情報など)

多次元場解法(数値流体力学、電磁気学)

コンウェイのライフゲームシミュレーションのプログラム。

状態推定

クワッドツリーは、フラクタル画像解析にも利用されます。

最大非結合集合数

クワッドツリー、つまり領域クワッドツリーは、画像処理のアプリケーションにうまく適応しています。領域クワッドツリーとそれらに対して行われる画像処理手順はカラー画像にも同様に適用できますが、ここではバイナリ画像データに限定して説明します。

画像処理にクワッドツリーを採用する利点は、和集合や交差などの集合演算を迅速かつ簡単に実行できることです。2 つのバイナリ イメージが与えられた場合、イメージ ユニオン (オーバーレイとも呼ばれます) は、入力イメージの 1 つに同じ場所に黒いピクセルが含まれている場合、ピクセルが黒いイメージを生成します。つまり、出力イメージのピクセルは、両方の入力イメージの一致するピクセルが白の場合にのみ白になります。それ以外の場合は黒です。ピクセル単位で演算を行う代わりに、クワッドツリーの容量を使用して複数のピクセルを 1 つのノードで表現することで、和集合を効率的に計算できます。以下の説明では、サブツリーに黒と白の両方のピクセルが含まれる場合、サブツリーのルートは灰色であると主張します。

このアルゴリズムは、出力クワッドツリー T_{1} を構築し T_{2} ながら 2 つの入力クワッドツリー ( と ) をトラバースすることで機能します T 。

非公式には、アルゴリズムは次のように説明されています。

{\displaystyle v_{1}\in T_{1}} 画像内の同じ領域に対応する {\displaystyle v_{2}\in T_{2}} ノードとを考えてみます。

v_{1} または v_{2} が黒の場合、対応するノードが黒で作成され、 T 黒色で表示されます。

一方が黒でもう一方が灰色の場合、一方だけが黒で、灰色のノードの下にはサブツリーがあります。

このサブツリーはナビゲートする必要はありません。

(それぞれ v_{1} 、)が白で、 v_{2} v_{2} その下のサブツリー(存在する場合)が にコピーされます v_{1} 。 T

両方と v_{1} が v_{2} 灰色の場合は、 と の対応する子 v_{1} v_{2} が考慮されます。

アルゴリズムは効果的ですが、それ自体では最小サイズのクワッドツリーを保証するものではありません。

たとえば、サイズのチェッカーボード (すべてのタイルがピクセル)  を {\displaystyle 2^{k}\times 2^{k}} その補数と結合した場合の結果を考えてみましょう。

結果は、ルートノード(黒色)のみを含む四分木で表されるはずの巨大な黒い正方形ですが、代わりにアルゴリズムは完全な4項の深さの木を生成します k 。

これを修正するには、結果のクワッドツリーのボトムアップ トラバーサルで、4 つの子ノードが同じ色であるかどうかを判断します。 この状況では、親を同色のリーフに置き換えます。

2 枚の写真の交差のアルゴリズムはほぼ同じです。2 つの画像の交差を概念化する 1 つのアプローチは、白いピクセルに関する結合としてです。その結果、交差を実行するために、union メソッドで黒と白の参照を切り替えます。

バイナリ画像で隣接する 2 つの黒いピクセルについて考えてみます。垂直または水平のエッジを共有している場合、それらは隣接しています。一般的に、2つの黒いピクセルは、隣接するピクセルのみをトラバースすることによって一方が他方から到達できる場合(つまり、連続する各ペアが隣接している間に黒いピクセルのパスがある場合)に関連しています。接続された黒のピクセルの最大コレクションは、コンポーネントを構成します。四分木画像形式を使用して、Samet このアプローチは、ポリゴンの色付けにも利用できます。

このアルゴリズムは、次の 3 つのフェーズで動作します。

隣接する黒ピクセルの関連付けを確立します

最初のステップの等価関係を処理して、接続された各コンポーネントの一意のラベルを取得します。

黒のピクセルを、その接続に対応するコンポーネントラベルで識別します。

わかりやすくするために、四分木のノードの子が Z オーダー (SW, NW, SE, NE) に従うと仮定します。この構造に頼ることができるので、クワッドツリーを参照して、特定のセルの階層のさまざまなレベルで近くのセルを識別する方法を知っています。

最初に、クワッドツリーのポストオーダートラバーサルが実行されます。

各黒い葉について v 、北隣と東隣のセルを表すノード(つまり、

のセルとエッジを共有する北側と東側のセル)。 v

木はZオーダーで構成されているため、南と西の隣人が世話をされ、説明されていることは間違いありません。

現在検討中の北または東の隣人を とします u 。

黒 u のピクセルを表す場合:

ラベルが 1 つしか u ない場合は v 、このラベルを反対側のセルに貼り付けます

ラベルを作成し、どちらもラベルがない場合は両方に割り当てます。

u ラベル v が異なる場合は、このラベルの等価性に注意して続行します。

ステップ 2 は、共用体検索データ構造で可能です。まず、各一意のラベルを独自のセットに分離します。第 1 段階で特定された等価接続ごとに、関連するセットが結合されます。残りの各セットは、個別の接続された画像コンポーネントに関連付けられます。

ステップ 3 では、2 回目のポストオーダー トラバーサルを実行します。

今回は、黒のノードごとに、 v union-findの検索操作(古いラベルが