Quadtree decomposition is an analysis technique that involves subdividing an image into blocks that are more homogeneous than the image itself. This technique reveals information about the structure of the image. It is also useful as the first step in adaptive compression algorithms.
You can perform quadtree decomposition using the
qtdecomp function. This function works by dividing a square image into
four equal-sized square blocks, and then testing each block to see if it meets some
criterion of homogeneity (e.g., if all the pixels in the block are within a specific
dynamic range). If a block meets the criterion, it is not divided any further. If it
does not meet the criterion, it is subdivided again into four blocks, and the test
criterion is applied to those blocks. This process is repeated iteratively until each
block meets the criterion. The result might have blocks of several different sizes.
Blocks can be as small as 1-by-1, unless you specify otherwise.
qtdecomp returns the quadtree decomposition as a sparse matrix, the
same size as
I. The nonzero elements represent the upper left corners
of the blocks. The value of each nonzero element indicates the block size.
This example shows how to perform quadtree decomposition on a 512-by-512 grayscale image.
Read the grayscale image into the workspace.
I = imread('liftingbody.png');
Perform the quadtree decomposition by calling the
qtdecomp function, specifying as arguments the image and the test criteria used to determine the homogeneity of each block in the decomposition. For example, the criterion might be a threshold calculation such as
max(block(:)) - min(block(:)) >= 0.27. You can also supply
qtdecomp with a function (rather than a threshold value) for deciding whether to split blocks. For example, you might base the decision on the variance of the block.
S = qtdecomp(I,0.27);
View a block representation of the quadtree decomposition. Each black square represents a homogeneous block, and the white lines represent the boundaries between blocks. Notice how the blocks are smaller in areas corresponding to large changes in intensity in the image.
blocks = repmat(uint8(0),size(S)); for dim = [512 256 128 64 32 16 8 4 2 1]; numblocks = length(find(S==dim)); if (numblocks > 0) values = repmat(uint8(1),[dim dim numblocks]); values(2:dim,2:dim,:) = 0; blocks = qtsetblk(blocks,S,dim,values); end end blocks(end,1:end) = 1; blocks(1:end,end) = 1; imshow(I), figure, imshow(blocks,)