The source code of iqdb contains a 2D Haar transform implementation. The author claims to have implemented it according to the paper "Fast Multiresolution Image Querying", which is freely available here.
This is the relevant text from the paper:
A standard two-dimensional Haar wavelet decomposition of an image is very simple to code. It involves a one-dimensional decomposition on each row of the image, followed by a one-dimensional decomposition on each column of the result.
The following pseudocode performs this one-dimensional decomposition on an array A of h elements, with h a power of two:
proc DecomposeArray (A : array[0..h-1] of color): A <- A / sqrt(h) while h > 1 do: h <- h/2 for i <- 0 to h-1 do: A'[i] <- (A[2i] + A[2i + 1]) / sqrt(2) A'[h+i] <- (A[2i] - A[2i + 1]) / sqrt(2) end for A <- A' end while end proc
In the pseudocode above, the entries of A are assumed to be 3dimensional color components, each in the range [0,1]. The various arithmetic operations are performed on the separate color components individually.
An entire r x r image T can thus be decomposed as follows:
proc DecomposeImage(T : array[0..r-1, 0..r-1] of color): for row <- 1 to r do: DecomposeArray(T[row, 0..r-1]) end for for col <- 1 to r do: DecomposeArray(T[0..r-1, col]) end for end proc
Implementing it this way does not produce results that match the example images in the majority of the articles I have found on the internet covering this topic, including the Wikipedia article.
Note: The image is divided into 4 large squares, and (only) the top left square is further divided into 4 squares.
However, I have also found counterexamples (i.e. examples that follow the scheme used in the paper above), e.g. here.
The question is whether to loop over all rows and columns, and doing the fully recursive transform in an inner loop for each row or column, - OR - doing one pass of recursion in the outermost loop, and within each single pass only processing the remaining rows and columns.
I have implemented both approaches to demonstrate the difference visually: https://bplu4t2f.github.io/wavelet_toy/
In the approach that wikipedia uses (which I call "pass major" because the pass of recursion is the outermost loop), the emerging pattern shows that each pass divides the image into 4 squares, and only the upper left square is modified in the next pass.
In the approach that iqdb uses (which I call "pass minor"), the emerging pattern shows that only the bottom right of the 4 divisions remains unchanged during subsequent passes.
The pass minor approach feels incorrect to me, because, when looking at it intuitively, it reprocesses parts of the image that have already been transformed during each pass, effectively applying a primitive edge detection scheme recursively on previosly detected edges. It doesn't seem to make much sense to me.
Which of these approaches is correctly being referred to as 2D Haar wavelet decomposition? To both approaches have a name?