オクトリー

八分木は、各内部ノードがちょうど 8つの子を持つツリー データ構造です。八分木は、3 次元空間を再帰的に 8 つの八分木に分割して分割するために最もよく使用されます。八分木は、四分木の 3 次元版です。この単語は、 oct (ギリシャ語で「8」を意味する) + treeから派生したものです。八分木は、3D グラフィックスや 3Dゲーム エンジンでよく使用されます。

八分木の各ノードは、それが表す空間を 8 つの八分円に分割します。ポイント領域 (PR) 八分木では、ノードは明示的な3 次元ポイントを格納します。これは、そのノードの分割の「中心」です。ポイントは、8 つの子のそれぞれについて、コーナーの 1 つを定義します。マトリックス ベース (MX) 八分木では、分割ポイントは暗黙的に、ノードが表す空間の中心です。PR 八分木のルート ノードは無限の空間を表すことができます。MX 八分木のルート ノードは、暗黙の中心が明確に定義されるように、有限の境界付き空間を表す必要があります。八分木はk -d ツリーと同じではないことに注意してください。k-d ツリーは次元に沿って分割され、八分木はポイントの周囲に分割されます。また、k - d ツリーは常にバイナリですが、八分木の場合はそうではありません。深さ優先探索を使用することで、ノードはトラバースされ、必要な表面のみが表示されます。

3Dコンピュータグラフィックスにおける八分木の使用は、レンセラー工科大学のドナルド・ミーガーによって開拓され、1980年の報告書「八分木エンコーディング：コンピュータによる任意の3Dオブジェクトの表現、操作、表示のための新しい技術」^[1]で説明されました。彼は、この論文で1995年に「八分木エンコーディングを使用した複雑なソリッドオブジェクトの高速画像生成」の 特許（1984年優先日）を取得しました^[2]。

• 3Dコンピュータグラフィックスにおける詳細レベルレンダリング^[3]
• 空間インデックス
• 最近傍探索^[4]
• 3次元での効率的な衝突検出
• 視錐台カリングの表示
• 高速多重極法
• 非構造化グリッド
• 有限要素解析
• スパースボクセル八分木^[5]
• 状態推定^[6]
• 集合推定^[7]

1988 年に Gervautz と Purgathofer によって発明されたoctreeカラー量子化アルゴリズムは、画像カラー データを最大 9 レベルの octree としてエンコードします。octree が使用されるのは、 RGBシステムには 3 つのカラー コンポーネントがあるためです。最上位レベルで分岐するノード インデックスは、赤、緑、青のカラー コンポーネントの最上位ビットを使用する式 (例: 4r + 2g + b) によって決定されます。次の下位レベルでは、次のビットの重要度が使用されます。以下同様に続きます。ツリー サイズを縮小するために、重要度の低いビットが無視されることもあります。 ${\displaystyle 2^{3}=8}$

このアルゴリズムは、ツリーのサイズを制限できるため、メモリ効率が非常に高くなります。オクトリーの最下位レベルは、ツリーに表されていない色データを取得するリーフ ノードで構成されます。これらのノードには、最初は 1 ビットが含まれます。必要なパレット色数よりもはるかに多くの色がオクトリーに入力された場合、最下位レベルのノードを探し、そのビット データをリーフ ノードまで平均化してツリーの一部を刈り込むことで、オクトリーのサイズを継続的に縮小できます。サンプリングが完了したら、ツリー内のすべてのルートをリーフ ノードまで探索し、途中のビットを書き留めると、必要な色数がほぼ得られます。

以下の再帰アルゴリズムのサンプルの概要 ( MATLAB構文) は、3 次元の点の配列を octree スタイルのビンに分解します。実装は、指定されたすべての点を囲む単一のビンから始まり、次に 8 つの octree 領域に再帰的に分割されます。指定された終了条件が満たされると、再帰は停止します。このような終了条件の例 (以下のコードに表示) は次のとおりです。

• ビンに含まれるポイントの数が指定数より少ない場合
• ビンの辺の長さに基づいてビンのサイズまたは容積が最小に達したとき
• 再帰が最大分割数に達したとき

関数[binDepths, binParents, binCorners, pointBins] = OcTree ( points ) 

binDepths = [ 0 ] % この基本レベルのビンでビンの深さの配列を初期化します。binParents = [ 0 ] % この基本レベルのビンは他のビンの子ではありません。binCorners = [ min ( points ) max ( points )] % XYZ 空間内のすべてのポイントを囲みます。pointBins (:) = 1 % 最初は、すべてのポイントがこの最初のビンに割り当てられます。divide ( 1 ) % この最初のビンの分割を開始します。       
      
    
      
           

関数divide ( binNo ) 

% このビンが終了条件を満たしている場合は、それ以上分割しません。
binPointCount = nnz ( pointBins == binNo ) binEdgeLengths = binCorners ( binNo , 1 : 3 ) - binCorners ( binNo , 4 : 6 ) binDepth = binDepths ( binNo ) exitConditionsMet = binPointCount < value || min ( binEdgeLengths ) < value || binDepth > value if exitConditionsMet return ; % 再帰関数を終了end    
      
  
          
 
     


% それ以外の場合は、新しい分割ポイントを使用して、このビンを 8 つの新しいサブビンに分割します。
newDiv = ( binCorners ( binNo , 1 : 3 ) + binCorners ( binNo , 4 : 6 )) / 2 for i = 1 : 8 newBinNo = length ( binDepths ) + 1 binDepths ( newBinNo ) = binDepths ( binNo ) + 1 binParents ( newBinNo ) = binNo binCorners ( newBinNo ) = [ minCornerまたはmaxCornerを持つnewDivの8 つのペアのうちの1つ] oldBinMask = pointBins == binNo % pointBins == binNo のどのポイントが newBinNo に属するかを計算します。pointBins ( newBinMask ) = newBinNo % この新しく作成されたビンを再帰的に分割します。除算( newBinNo )終了        
   
        
        
      
                 
        
    
      
    
    

24 ビット RGB 画像の全色リストを、上で説明したオクツリー ポイント分解実装へのポイント入力として取り、オクツリー カラー量子化の結果を示す例を次に示します。最初の画像は元の画像 (532818 の異なる色) で、2 番目はオクツリー分解を使用して量子化された画像 (184 の異なる色) です。各ピクセルには、そのピクセルが属するオクツリー ビンの中心にある色が割り当てられています。あるいは、最終的な色は各オクツリー ビンのすべての色の重心で選択することもできますが、この追加計算は視覚的な結果にほとんど影響しません。^[8]

% 元の RGB イメージを読み取ります
Img = imread ( 'IMG_9980.CR2' ); % ピクセルを RGB ポイント トリプレットとして抽出しますpts = reshape ( Img , [], 3 ); % ターゲット ビン容量を使用して OcTree 分解オブジェクトを作成しますOT = OcTree ( pts , ' BinCapacity ' , ceil (( size ( pts , 1 ) / 256 ) * 7 )); % octree オブジェクト上の「リーフ ノード」であるビンを検索しますleafs = find ( ~ ismember ( 1 : OT.BinCount , OT.BinParents ) & ... ismember ( 1 : OT.BinCount , OT.PointBins ) ) ; % 各リーフ ビンの中心 RGB 位置を検索しますbinCents = mean ( reshape ( OT . BinBoundaries ( leafs ,:), [], 3 , 2 ), 3 ); % カラー マップを使用して新しい「インデックス付き」イメージを作成しますImgIdx = zeros ( size ( Img , 1 ), size ( Img , 2 )); for i = 1 : length ( leafs ) pxNos = find ( OT . PointBins == leafs ( i )); ImgIdx ( pxNos ) = i ; end ImgMap = binCents / 255 ; % 8ビットカラーをMATLABのRGB値に変換します% 元の532818色の画像と結果の184色の画像を表示します図subplot ( 1,2,1 ) , imshow ( Img ) title ( sprintf ( '元の%d色の画像' ,  

    

         

     
     

      
 

     
   
      
      

     
 


   
 size ( unique ( pts , 'rows' ), 1 ))) subplot ( 1 , 2 , 2 ), imshow ( ImgIdx , ImgMap ) title ( sprintf ( 'Octree 量子化された %d カラー画像' , size ( ImgMap , 1 ))) 
    
  

• バイナリ空間分割
• 境界間隔階層
• Cube 2: Sauerbraten は、ジオメトリがほぼ完全に八分木に基づいている 3D ゲーム エンジンです。
• id Tech 6は、オクツリーに格納されたボクセルを利用する3Dゲームエンジンです。
• Irrlicht エンジン、八分木シーンノードをサポート
• クレーの測度問題
• 線形八分木
• OGRE は、八分木シーンマネージャの実装を持っています
• 下地舗装
• ボクセル
• クワッドツリー

ウィキメディア・コモンズには、オクツリーに関連するメディアがあります。

• Microsoft Systems Journal における Octree Quantization
• ドクター・ドブスのオクツリーを使ったカラー量子化
• オクトリーカラー量子化の概要
• Sojan Lal, P.; Unnikrishnan, A.; Poulose Jacob, K. (1998). 「オクトツリー生成アルゴリズムの並列実装」。1998 国際画像処理会議議事録。 ICIP98 (カタログ番号 98CB36269)。 第 3 巻。 pp. 1005–1009。doi :10.1109/ICIP.1998.727419。ISBN 0-8186-8821-1. S2CID  195863788。
• 情報損失を減らしたラスタースキャンからのオクツリーの生成、P. Sojan Lal、A Unnikrishnan、K Poulose Jacob、IASTED 国際会議 VIIP 2001 [1] ^{[永久リンク切れ‍ ]}
• 有限要素アプリケーションのための並列八分木
• ビデオ: 状態推定における八分木の使用