Octree - Octree

Image
Stânga: Subdiviziune recursivă a unui cub în octanți . Dreapta: octree corespunzător.

Un octree este o structură de date în arbore în care fiecare nod intern are exact opt copii . Octree sunt cel mai adesea folosite pentru partiționarea unui spațiu tridimensional prin împărțirea recursivă în opt octanți. Octree sunt analogul tridimensional al quadtrees . Cuvântul este derivat din oct (rădăcină greacă care înseamnă „opt”) + copac . Octree sunt adesea folosite în grafica 3D și motoarele de jocuri 3D .

Pentru reprezentarea spațială

Fiecare nod dintr-un octree împarte spațiul pe care îl reprezintă în opt octanți . Într-o regiune de punct (PR) octree, nodul stochează un punct tridimensional explicit , care este „centrul” subdiviziunii pentru acel nod; punctul definește unul dintre colțurile pentru fiecare dintre cei opt copii. Într-un octree bazat pe matrice (MX), punctul de subdiviziune este implicit centrul spațiului pe care îl reprezintă nodul. Nodul rădăcină al unui octree PR poate reprezenta spațiu infinit; nodul rădăcină al unui octree MX trebuie să reprezinte un spațiu delimitat finit astfel încât centrele implicite să fie bine definite. Rețineți că Octree nu sunt la fel ca copacii k -d : copacii k -d se împart de-a lungul unei dimensiuni și octrei se împart în jurul unui punct. De asemenea, copacii k- d sunt întotdeauna binari, ceea ce nu este cazul octreilor. Prin utilizarea unei căutări în profunzime , nodurile trebuie parcurse și trebuie vizualizate numai suprafețele necesare.

Istorie

Utilizarea octreelor ​​pentru grafica computerizată 3D a fost inițiată de Donald Meagher la Institutul Politehnic Rensselaer , descris într-un raport din 1980 „Octree Encoding: A New Technique for the Representation, Manipulation and Display of Arbitenary 3-D Objects by Computer”, pentru care el deține un brevet din 1995 (cu o dată de prioritate din 1984 ) „Generarea de imagine de mare viteză a obiectelor solide complexe folosind codificare octree”

Utilizări comune

Aplicarea la cuantizarea culorilor

Octree culoare cuantizare algoritm, inventat de Gervautz și Purgathofer în 1988, codifică datele de culoare de imagine ca octree până la nouă niveluri de adâncime. Octree sunt utilizate pentru că există trei componente de culoare în sistemul RGB . Indicele nodului pentru a se ramifica de la nivelul superior este determinat de o formulă care utilizează cei mai semnificativi biți ai componentelor de culoare roșie, verde și albastră, de exemplu 4r + 2g + b. Următorul nivel inferior folosește următoarea semnificație a bitului și așa mai departe. Biții mai puțin semnificativi sunt uneori ignorați pentru a reduce dimensiunea copacului.

Algoritmul este foarte eficient din punct de vedere al memoriei, deoarece dimensiunea arborelui poate fi limitată. Nivelul inferior al octreei constă din noduri de frunze care acumulează date de culoare care nu sunt reprezentate în copac; aceste noduri conțin inițial biți unici. Dacă se introduce mult mai mult decât numărul dorit de culori ale paletei în octree, dimensiunea sa poate fi redusă continuu prin căutarea unui nod de nivel inferior și media datelor sale de biți într-un nod frunză, tăind o parte a arborelui. Odată ce eșantionarea este completă, explorarea tuturor rutelor din copac până la nodurile frunzei, luând notă de biții de-a lungul drumului, va produce aproximativ numărul necesar de culori.

Implementare pentru descompunerea punctelor

Exemplul schiței algoritmului recursiv de mai jos ( sintaxa MATLAB ) descompune o serie de puncte tridimensionale în coșuri în stil octree. Implementarea începe cu un singur coș care înconjoară toate punctele date, care apoi se împarte recursiv în cele 8 regiuni ale acestuia. Recursivitatea este oprită atunci când este îndeplinită o anumită condiție de ieșire. Exemple de astfel de condiții de ieșire (prezentate în codul de mai jos) sunt:

  • Când un coș de gunoi conține mai puțin de un număr dat de puncte
  • Când un coș de gunoi atinge o dimensiune sau un volum minim în funcție de lungimea marginilor sale
  • Când recursivitatea a atins un număr maxim de subdiviziuni
function [binDepths,binParents,binCorners,pointBins] = OcTree(points)
 
binDepths = [0]     % Initialize an array of bin depths with this single base-level bin
binParents = [0]    % This base level bin is not a child of other bins
binCorners = [min(points) max(points)] % It surrounds all points in XYZ space
pointBins(:) = 1    % Initially, all points are assigned to this first bin
divide(1)           % Begin dividing this first bin
 
function divide(binNo)
    
% If this bin meets any exit conditions, do not divide it any further.
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; % Exit recursive function
end
 
% Otherwise, split this bin into 8 new sub-bins with a new division point
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) = [one of the 8 pairs of the newDiv with minCorner or maxCorner]
    oldBinMask = pointBins==binNo
    % Calculate which points in pointBins==binNo now belong in newBinNo 
    pointBins(newBinMask) = newBinNo
    % Recursively divide this newly created bin
    divide(newBinNo)
end

Exemplu de cuantizare a culorilor

Luând lista completă a culorilor unei imagini RGB pe 24 de biți ca punct de intrare la implementarea descompunerii punctului Octree prezentat mai sus, următorul exemplu arată rezultatele cuantificării culorii octree. Prima imagine este originală (532818 culori distincte), în timp ce a doua este imaginea cuantificată (184 culori distincte) folosind descompunerea octree, cu fiecare pixel atribuită culoarea în centrul coșului octree în care se încadrează. Alternativ, culorile finale ar putea fi alese la centroidul tuturor culorilor din fiecare coș de octri, cu toate acestea acest calcul adăugat are un efect foarte mic asupra rezultatului vizual. 

% Read the original RGB image
Img = imread('IMG_9980.CR2');
% Extract pixels as RGB point triplets
pts = reshape(Img,[],3);
% Create OcTree decomposition object using a target bin capacity
OT = OcTree(pts,'BinCapacity',ceil((size(pts,1) / 256) *7));
% Find which bins are "leaf nodes" on the octree object
leafs = find(~ismember(1:OT.BinCount, OT.BinParents) & ...
    ismember(1:OT.BinCount,OT.PointBins));
% Find the central RGB location of each leaf bin
binCents = mean(reshape(OT.BinBoundaries(leafs,:),[],3,2),3);
 
% Make a new "indexed" image with a color map
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; % Convert 8-bit color to MATLAB rgb values
 
% Display the original 532818-color image and resulting 184-color image 
figure
subplot(1,2,1), imshow(Img)
title(sprintf('Original %d color image', size(unique(pts,'rows'),1)))
subplot(1,2,2), imshow(ImgIdx, ImgMap)
title(sprintf('Octree-quantized %d color image', size(ImgMap,1)))

Vezi si

Referințe

linkuri externe