Memory consumption of the quad tree

Please, what is the memory consumption of the recursive quad tree decomposition procedure [S = qtdecomp(I)] with respect to the input set I?

[Umar]

Hi @ Ali Al-Janabi,

The memory consumption of the recursive quad tree decomposition procedure (S = qtdecomp(I)) depends on the number of nodes created during the subdivision process, which is influenced by the characteristics of the input set I.

[Ali Al-Janabi]

Thank you

[Umar]

No problem, Ali. Glad to help out. Please let us know if you have any further questions.

Answer 1

[R]

Hi @Ali Al-Janabi

The memory consumption of the recursive quadtree decomposition procedure S = qtdecomp(I) with respect to the input set I can be characterized as follows:

1. Size of Input Image (I): The memory required to store the input image I remains ( O(m x n) ).
2. Quadtree Structure: The quadtree decomposition process recursively divides the image into four equal-sized blocks until each block meets the homogeneity criterion. This means that the number of blocks and their sizes can vary depending on the image's complexity. In the worst-case scenario, where the image is highly detailed and requires maximum subdivision, the memory consumption for the quadtree structure can approach ( O(m x n) ). This is because, in the worst case, each pixel might be represented as an individual block.
3. Storage of Decomposition Information: The output S includes information about the coordinates and sizes of the blocks. The memory required for this information depends on the number of blocks created during the decomposition. If k is the number of blocks, the memory consumption for storing the decomposition information is ( O(k) ). In the worst case, ( k ) can be as large as ( m x n ).

A lower threshold in qtdecomp leads to more subdivisions and higher memory consumption, potentially ( O(m x n) ). A higher threshold results in fewer subdivisions and lower memory usage.

% Load a sample grayscale image
I = imread('cameraman.tif');

% Display the original image
figure;
imshow(I);
title('Original Image');

% Perform quadtree decomposition
threshold = 0.4; % Threshold for splitting blocks
S = qtdecomp(I, threshold);

% Display the quadtree decomposition result
blocks = repmat(uint8(0), size(I));
for dim = [512 256 128 64 32 16 8 4 2 1]
    numblocks = length(find(S == dim));
    if numblocks > 0
        values = repmat(uint8(255), [dim dim numblocks]);
        blocks = qtsetblk(blocks, S, dim, values);
    end
end

% Analyze memory consumption
info = whos('I', 'S');
memoryUsage = sum([info.bytes]);

fprintf('Memory consumption for the input image I: %d bytes\n', info(1).bytes);

Memory consumption for the input image I: 65536 bytes

fprintf('Memory consumption for the quadtree decomposition S: %d bytes\n', info(2).bytes);

Memory consumption for the quadtree decomposition S: 70136 bytes

fprintf('Total memory consumption: %d bytes\n', memoryUsage);

Total memory consumption: 135672 bytes

Refer to the documentation of qtdecomp for more information: Quadtree decomposition - MATLAB qtdecomp (mathworks.com)

[Ali Al-Janabi]

Hi @R Thank you for this useful information. Please is there any published paper or book that mentions this?