Algorithm used to implement the function qtdecomp?

I am wondering if anyone is familiar with the algorithm used to implement the qtdecomp function in the image processing toolbox. I am working on my masters thesis and am trying to compare results of my proposed algorithm vs other existing algorithms and the qtdecomp function was a useful tool for early simulation results and I am wanting to be as accurate as possible when comparing my results.

Answer 1

[Mike Croucher]

There is a description of the algorithm on the documentation page qtdecomp. It says

"The qtdecomp function divides a square image into four equal-sized square blocks, and then tests each block to see if it meets some criterion of homogeneity. 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 can have blocks of several different sizes."

In the comments section you asked about the homogeneity criteria. I asked internally and the default is simply to test if they are all exactly equal. This is also mentioned in the doc. It depends on the syntax used:

S = qtdecomp(I) performs a quadtree decomposition on the grayscale image I and returns the quadtree structure in the sparse matrix S. By default, qtdecomp splits a block unless all elements in the block are equal.

Then for threshold

S = qtdecomp(I,threshold) splits a block if the maximum value of the block elements minus the minimum value of the block elements is greater than threshold.

You can come up with your own function to determine if a block should be split or not:

S = qtdecomp(I,fun) uses the function fun to determine whether to split a block.

Does that help?

[Joe]

Ya the description gives a general overview of quadtree decomposition. I guess my question is more specifically about the line "meets some criteria of homogeneity." How is homogeneity determined with this function? Does it use a mean square error critreia with a fixed threshold (my current assumption since one of the function paramaters is a threshold) or does it use some other homogeneity critreia?

[Mike Croucher]

I'll ask internally and see what I can find

[Joe]

That would be fantastic, thank you!

[Mike Croucher]

Updated with more details.

[Joe]

That is super helpful, thank you!