| Octree | |||||||||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Type | Tree | ||||||||||||||||||||||||||
| Invented | 1980 | ||||||||||||||||||||||||||
| Invented by | Donald Meagher | ||||||||||||||||||||||||||
| |||||||||||||||||||||||||||
Anoctree is atree data structure in which eachinternal node has exactly eightchildren. Octrees are most often used to partition athree-dimensional space byrecursively subdividing it into eightoctants. Octrees are the three-dimensional analog ofquadtrees. The word is derived fromoct (Greek root meaning "eight") +tree. Octrees are often used in3D graphics and 3Dgame engines.
Each node in an octree subdivides the space it represents into eightoctants. In a point region (PR) octree, the node stores an explicitthree-dimensional point, which is the "center" of the subdivision for that node; the point defines one of the corners for each of the eight children. In a matrix-based (MX) octree, the subdivision point is implicitly the center of the space the node represents. The root node of a PR octree can represent infinite space; the root node of an MX octree must represent a finite bounded space so that the implicit centers are well-defined. Note that octrees are not the same ask-d trees:k-d trees split along a dimension and octrees split around a point. Alsok-d trees are always binary, which is not the case for octrees.By using adepth-first search the nodes are to be traversed and only required surfaces are to be viewed.
The use of octrees for3D computer graphics was pioneered by Donald Meagher atRensselaer Polytechnic Institute, described in a 1980 report "Octree Encoding: A New Technique for the Representation, Manipulation and Display of Arbitrary 3-D Objects by Computer",[1] for which he holds a 1995 patent (with a 1984priority date) "High-speed image generation of complex solid objects using octree encoding"[2]
The octreecolor quantization algorithm, invented by Gervautz and Purgathofer in 1988, encodes image color data as an octree up to nine levels deep. Octrees are used because and there are three color components in theRGB system. The node index to branch out from at the top level is determined by a formula that uses the most significant bits of the red, green, and blue color components, e.g. 4r + 2g + b. The next lower level uses the next bit significance, and so on. Less significant bits are sometimes ignored to reduce the tree size.
The algorithm is highly memory efficient because the tree's size can be limited. The bottom level of the octree consists of leaf nodes that accrue color data not represented in the tree; these nodes initially contain single bits. If much more than the desired number of palette colors are entered into the octree, its size can be continually reduced by seeking out a bottom-level node and averaging its bit data up into a leaf node, pruning part of the tree. Once sampling is complete, exploring all routes in the tree down to the leaf nodes, taking note of the bits along the way, will yield approximately the required number of colors.
The example recursive algorithm outline below (MATLAB syntax) decomposes an array of 3-dimensional points into octree style bins. The implementation begins with a single bin surrounding all given points, which then recursively subdivides into its 8 octree regions. Recursion is stopped when a given exit condition is met. Examples of such exit conditions (shown in code below) are:
function[binDepths, binParents, binCorners, pointBins] = OcTree(points)binDepths=[0]% Initialize an array of bin depths with this single base-level binbinParents=[0]% This base level bin is not a child of other binsbinCorners=[min(points)max(points)]% It surrounds all points in XYZ spacepointBins(:)=1% Initially, all points are assigned to this first bindivide(1)% Begin dividing this first binfunctiondivide(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>valueifexitConditionsMetreturn;% Exit recursive functionend% Otherwise, split this bin into 8 new sub-bins with a new division pointnewDiv=(binCorners(binNo,1:3)+binCorners(binNo,4:6))/2fori=1:8newBinNo=length(binDepths)+1binDepths(newBinNo)=binDepths(binNo)+1binParents(newBinNo)=binNobinCorners(newBinNo)=[oneofthe8pairsofthenewDivwithminCornerormaxCorner]oldBinMask=pointBins==binNo% Calculate which points in pointBins == binNo now belong in newBinNopointBins(newBinMask)=newBinNo% Recursively divide this newly created bindivide(newBinNo)end
Taking the full list of colors of a 24-bit RGB image as point input to the Octree point decomposition implementation outlined above, the following example show the results of octree color quantization. The first image is the original (532818 distinct colors), while the second is the quantized image (184 distinct colors) using octree decomposition, with each pixel assigned the color at the center of the octree bin in which it falls. Alternatively, final colors could be chosen at the centroid of all colors in each octree bin, however this added computation has very little effect on the visual result.[8]
% Read the original RGB imageImg=imread('IMG_9980.CR2');% Extract pixels as RGB point tripletspts=reshape(Img,[],3);% Create OcTree decomposition object using a target bin capacityOT=OcTree(pts,'BinCapacity',ceil((size(pts,1)/256)*7));% Find which bins are "leaf nodes" on the octree objectleafs=find(~ismember(1:OT.BinCount,OT.BinParents)&...ismember(1:OT.BinCount,OT.PointBins));% Find the central RGB location of each leaf binbinCents=mean(reshape(OT.BinBoundaries(leafs,:),[],3,2),3);% Make a new "indexed" image with a color mapImgIdx=zeros(size(Img,1),size(Img,2));fori=1:length(leafs)pxNos=find(OT.PointBins==leafs(i));ImgIdx(pxNos)=i;endImgMap=binCents/255;% Convert 8-bit color to MATLAB rgb values% Display the original 532818-color image and resulting 184-color imagefiguresubplot(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)))
