Lokakuu - Octree

Image
Vasen: Kuution rekursiivinen jakaminen oktanteiksi . Oikea: vastaava oktri.

Octree on puu tietorakenne , jossa jokainen sisäinen solmu on täsmälleen kahdeksan lasta . Octrees ovat useimmiten käytetään osioida kolmiulotteisessa avaruudessa by rekursiivisesti jakamalla se kahdeksaan octants. Octrees ovat kolmiulotteisia analogi quadtrees . Sana on johdettu okt (kreikan juuri tarkoittaa "kahdeksan") + puu . Oktereita käytetään usein 3D -grafiikassa ja 3D -pelimoottoreissa .

Tilaedustusta varten

Jokainen okterin solmu jakaa edustamansa tilan kahdeksaan oktanttiin . Pistealueen (PR) oktreissa solmu tallentaa selkeän kolmiulotteisen pisteen , joka on kyseisen solmun alajaon "keskipiste"; kohta määrittelee kulman jokaiselle kahdeksalle lapselle. Matriisipohjaisessa (MX) oktreissa alijakopiste on implisiittisesti solmun edustaman tilan keskipiste. PR -oktrin juurisolmu voi edustaa ääretöntä tilaa; MX-oktree-juurisolmun on edustettava äärellistä rajoitettua tilaa, jotta implisiittiset keskukset ovat hyvin määriteltyjä. Huomaa, että Octrees ei ole sama kuin k -d puut : k -d puut jakautuvat mittaa pitkin ja oktareet jakautuvat pisteen ympärille. Myös k -d -puut ovat aina binäärisiä, mikä ei pidä paikkaansa oktareissa. Käyttämällä syvyyssuuntaista hakua solmut on läpäistävä ja vain vaadittuja pintoja on tarkasteltava.

Historia

Oktareiden käytön 3D-tietokonegrafiikassa aloitti Donald Meagher Rensselaerin ammattikorkeakoulusta , joka on kuvattu vuoden 1980 raportissa "Octree Encoding: A New Technique for the representation, Manipulation and Display of mielivaltaiset 3D-objektit tietokoneella", jota varten hän omistaa vuoden 1995 patentin (jonka prioriteettipäivä on 1984 ) "Monimutkaisten kiinteiden objektien nopea kuvanmuodostus oktree-koodauksella"

Yleisiä käyttötarkoituksia

Sovellus värikvantisointiin

Octree väri kvantisointi -algoritmi, jonka keksi Gervautz ja Purgathofer vuonna 1988, koodaa kuvan väri tiedot kuin octree jopa yhdeksän tasoa syvä. Oktreja käytetään, koska RGB -järjestelmässä on kolme värikomponenttia . Ylätason haarautuvan solmun indeksi määritetään kaavalla, joka käyttää punaisen, vihreän ja sinisen värikomponenttien merkittävimpiä bittejä, esim. 4r + 2g + b. Seuraava alempi taso käyttää seuraavan bitin merkitystä jne. Vähemmän merkittäviä bittejä jätetään joskus huomiotta puun koon pienentämiseksi.

Algoritmi on erittäin muistitehokas, koska puun kokoa voidaan rajoittaa. Oktereen alin taso koostuu lehtisolmuista, jotka keräävät väritietoja, joita ei ole puussa; nämä solmut sisältävät alun perin yksittäisiä bittejä. Jos oktreettiin syötetään paljon enemmän kuin haluttu määrä paletin värejä, sen kokoa voidaan pienentää jatkuvasti etsimällä pohjatason solmu ja keskiarvoistamalla sen bittitiedot lehtisolmuun, karsimalla osa puusta. Kun näytteenotto on valmis, tutkimalla kaikkia puun reittejä lehtisolmuihin saakka huomioiden matkan varrella olevat bitit saadaan noin tarvittava määrä värejä.

Toteutus pisteen hajoamiseen

Alla oleva esimerkki rekursiivisesta algoritmista ( MATLAB- syntaksi) hajottaa 3-ulotteisten pisteiden taulukon oktreetyylisiksi lokeroiksi. Toteutus alkaa yhdellä säiliöllä, joka ympäröi kaikki annetut pisteet, joka jakautuu sitten rekursiivisesti sen 8 hehtaarin alueisiin. Rekursio pysäytetään, kun tietty poistumisedellytys täyttyy. Esimerkkejä tällaisista poistumisolosuhteista (esitetty alla olevassa koodissa) ovat:

  • Kun roskakorissa on vähemmän kuin tietty määrä pisteitä
  • Kun säiliö saavuttaa vähimmäiskoon tai tilavuuden sen reunojen pituuden perusteella
  • Kun rekursio on saavuttanut enimmäismäärän alajakoja
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

Esimerkki värikvantisoinnista

Kun 24-bittisen RGB-kuvan koko väriluettelo otetaan pisteeksi edellä kuvatun Octree-pisteiden hajotuksen toteutukseen, seuraava esimerkki näyttää oktreettisten värikvantisoinnin tulokset. Ensimmäinen kuva on alkuperäinen (532818 eri väriä), kun taas toinen on kvantisoitu kuva (184 eri väriä), jotka käyttävät oktreiden hajoamista. Vaihtoehtoisesti lopulliset värit voitaisiin valita jokaisen oktareerasian kaikkien värien keskipisteestä, mutta tällä lisätyllä laskennalla ei ole juurikaan vaikutusta visuaaliseen tulokseen. 

% 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)))

Katso myös

Viitteet

Ulkoiset linkit