IakovlevIA
commented
3 years ago You may already have noticed it, and I'm just commenting that the code could be sped up substantially if we simplify the expression by applying an inequality and telescoping. You should also check yourself whether or not what I'm saying is correct. C=0.5*(O{0,0}-O{N,N}). This expression is much quicker to compute than the original expression.
I fully agree with you that in this particular case presented in the paper you can simplify the equation for C this way. However, to distinguish between pictures with the same total complexity you can analyze the partial contributions C_k from different scales (see Fig.8 and the related discussion). In case of training neural networks, I would use C_k along with/instead of C to keep as much information about the sample as possible.
hannnwang
cainiao123s
You may already have noticed it, and I'm just commenting that the code could be sped up substantially if we simplify the expression by applying an inequality and telescoping. You should also check yourself whether or not what I'm saying is correct.
Equation [4] in the paper can be simplified with the following steps: 1) From an inequality, we can get rid of the absolute sign: We denote the image at step k to be A, and the image at step k+1 to be B. Following your explanations in the paper, B would be re-scaled and thus have the same dimension as A. Suppose they are also square images (generalizations to nonsquare images should be straightforward) and denote the image width or height to be L. Then, L^2O_{k+1,k} is the sum of pixelwise product of A and B, and L^2O{k,k} is the pixelwise product of A and A itself etc. One pixel of A or B is denoted as Aij and Bij respectively. Then, the term under the summation on the RHS of equation [4] can be expressed as |\sum{i,j} AijBij-1/2(AijAij+BijBij)|/L^2. At each (i,j), AijBij-1/2(AijAij+BijBij) is less than or equal to 0. This can be seen from the inequality: ab\leq 1/2(a^2+b^2) if a and b are real. (To prove it, simply subtract the RHS with LHS, and you get 1/2(a-b)^2, which is larger than or equal to 0.) Therefore, the term inside the absolute value sign should be always non-positive. We can then delete the absolute value sign, and add a minus sign in front of every term on the RHS of equation [4].
2) Apply the equation [3] you derived, and replace O{k+1,k} with O{k+1,k+1}. Combined with step 1), the term under the summation is turned into:
0.5*(O{k,k}-O{k+1,k+1})
3) Now, this series can be telescoped: if one sums the above expression from k=0 to k=N-1, then a lot of terms will cancel out. After summing over k, we can now convert equation [4] into: C=0.5*(O{0,0}-O{N,N}).
This expression is much quicker to compute than the original expression.
I have verified that this gives me the same results as the original expression when I apply it onto examples shown in Fig.1 and Fig.2 of the paper. (My results are different from what's listed in the paper, though, as explained in Issue #2.)
Caveats: Step 1) holds only if the pixels values are real numbers. Step 1) and 2) holds only if the definition of overlap and the coarse-graining process are done in the same way as in paper (illustrated by Fig.1 of the paper).